/* CIFgen.c -
 *
 *	This file provides routines that generate CIF from Magic
 *	tile information, using one of the styles read from the
 *	technology file.
 *
 *     *********************************************************************
 *     * Copyright (C) 1985, 1990 Regents of the University of California. *
 *     * Permission to use, copy, modify, and distribute this              *
 *     * software and its documentation for any purpose and without        *
 *     * fee is hereby granted, provided that the above copyright          *
 *     * notice appear in all copies.  The University of California        *
 *     * makes no representations about the suitability of this            *
 *     * software for any purpose.  It is provided "as is" without         *
 *     * express or implied warranty.  Export of this software outside     *
 *     * of the United States of America may require an export license.    *
 *     *********************************************************************
 */

#ifndef lint
static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/cif/CIFgen.c,v 1.23 2010/06/24 20:35:54 tim Exp $";
#endif  /* not lint */

#include <stdio.h>
#include <stdlib.h>             /* for abs() */
#include <math.h>		/* for ceil() and sqrt() */

#include "utils/magic.h"
#include "utils/geometry.h"
#include "tiles/tile.h"
#include "utils/hash.h"
#include "database/database.h"
#include "cif/CIFint.h"
#include "calma/calma.h"	/* for CalmaContactArrays */
#include "commands/commands.h"	/* for CmdFindNetProc()	*/
#include "select/selInt.h"	/* for select use and def */
#include "select/select.h"
#include "utils/stack.h"
#include "utils/malloc.h"
#include "utils/maxrect.h"

/* TRUE to run (very slow) algorithm for optimizing non-manhattan tiles */
/* (cuts size of output;  see also the GDS "merge" option)		*/
bool CIFUnfracture = FALSE;

/* The following global arrays hold pointers to the CIF planes
 * generated by the procedures in this module.  There are two
 * kinds of planes:  real CIF, which will ostensibly be output,
 * and temporary layers used to build up more complex geometric
 * functions.
 */

global Plane *CIFPlanes[MAXCIFLAYERS];

/* The following are paint tables used by the routines that implement
 * the geometric operations on mask layers, such as AND, OR, GROW,
 * etc.  There are really only two tables.  The first will paint
 * CIF_SOLIDTYPE over anything else, and the second will paint
 * space over anything else.  These tables are used on planes with
 * only two tile types, TT_SPACE and CIF_SOLIDTYPE, so they only
 * have two entries each.
 */

PaintResultType CIFPaintTable[] = {CIF_SOLIDTYPE, CIF_SOLIDTYPE};
PaintResultType CIFEraseTable[] = {TT_SPACE, TT_SPACE};

/* The following local variables are used as a convenience to pass
 * information between CIFGen and the various search functions.
 */

static int growDistance;	/* Distance to grow stuff. */
static Plane *cifPlane;		/* Plane acted on by search functions. */
static int cifScale;		/* Scale factor to use on tiles. */

extern void cifClipPlane();
extern void cifGenClip();

/*
 * ----------------------------------------------------------------------------
 *
 * cifPaintFunc --
 *
 * 	This search function is called during CIF_AND and CIF_OR
 *	and CIF_ANDNOT operations for each relevant tile.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	For the area of the tile, either paints or erases in
 *	cifNewPlane, depending on the paint table passed as parameter.
 *	The tile's area is scaled by cifScale first.
 * ----------------------------------------------------------------------------
 */

int
cifPaintFunc(tile, table)
    Tile *tile;
    PaintResultType *table;		/* Used for painting. */
{
    Rect area;

    TiToRect(tile, &area);
    area.r_xbot *= cifScale;
    area.r_xtop *= cifScale;
    area.r_ybot *= cifScale;
    area.r_ytop *= cifScale;

    DBNMPaintPlane(cifPlane, TiGetTypeExact(tile), &area, table,
		(PaintUndoInfo *) NULL);
    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowMinFunc --
 *
 * 	Called for each relevant tile during grow-min operations.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	May paint into cifNewPlane
 *
 * Algorithm (based on maximum horizontal stripes rule):
 *	Scan top and bottom boundaries from left to right.  For any
 *	distance (including distance zero) sharing the same type (0 or 1)
 *	on both the tile top and bottom, find the diagonal length.  If
 *	less than co_distance, then expand this area and paint.
 *	NOTE:  This algorithm does not cover a number of geometry cases
 *	and needs to be reworked.  It should be restricted to cases of
 *	layers that have "rect_only" DRC rules.  Since the rule is usually
 *	needed for implants on FET gates to maintain the implant width for
 *	small gates, the "rect_only" requirement is not particularly
 *	constraining.
 *
 * ----------------------------------------------------------------------------
 */

int
cifGrowMinFunc(tile, table)
    Tile *tile;
    PaintResultType *table;		/* Table to be used for painting. */
{
    Rect area, parea;
    int locDist, width, height, h;
    TileType type, tptype;
    Tile *tp, *tp2;
    bool changed;
    void SetMinBoxGrid();		/* Forward reference */

    TiToRect(tile, &area);

    area.r_xbot *= cifScale;
    area.r_xtop *= cifScale;
    area.r_ybot *= cifScale;
    area.r_ytop *= cifScale;

    parea = area;
    changed = FALSE;

    /* Check whole tile for minimum width */
    width = area.r_xtop - area.r_xbot;
    if (width < growDistance)
    {
	locDist = (growDistance - width) / 2;
	area.r_xbot -= locDist;
	area.r_xtop += locDist;

	/* If there is another tile on top or bottom, and the height is	*/
	/* less than minimum, then extend height in the direction of	*/
	/* the bordering tile.  Otherwise, if the height is less than	*/
	/* minimum, then grow halfway in both directions.		*/

	height = area.r_ytop - area.r_ybot;
	if (height < growDistance)
	{
	    bool freeTop, freeBot;

	    freeTop = freeBot = TRUE;

	    for (tp = LB(tile); LEFT(tp) < RIGHT(tile); tp = TR(tp))
		if (TiGetTopType(tp) == TiGetBottomType(tile))
		{
		    freeBot = FALSE;
		    break;
		}

	    for (tp2 = RT(tile); RIGHT(tp2) > LEFT(tile); tp2 = BL(tp2))
		if (TiGetBottomType(tp2) == TiGetTopType(tile))
		{
		    freeTop = FALSE;
		    break;
		}

	    /* In the following, value h ensures that the euclidean */
	    /* distance between inside corners of the layer	    */
	    /* satisfies growDistance.				    */

	    if (freeTop == TRUE && freeBot == FALSE)
	    {
		locDist = (growDistance - height) / 2;
		h = (int)sqrt((double)(growDistance * growDistance) -
			    0.25 * (double)((growDistance + width) *
			    (growDistance + width)) + 0.5);
		area.r_ybot -= h;
		changed = TRUE;
	    }
	    else if (freeTop == FALSE && freeBot == TRUE)
	    {
		h = (int)sqrt((double)(growDistance * growDistance) -
			    0.25 * (double)((growDistance + width) *
			    (growDistance + width)) + 0.5);
		area.r_ytop += h;
		changed = TRUE;
	    }
	    else {
		locDist = (growDistance - height) / 2;
		area.r_ybot -= locDist;
		area.r_ytop += locDist;
		changed = TRUE;
	    }
	}
    }

    /* Ensure grid limit is not violated */
    if (changed) SetMinBoxGrid(&area, growDistance);

    DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

    area = parea;

    /* Scan bottom from left to right */
    for (tp = LB(tile); LEFT(tp) < RIGHT(tile); tp = TR(tp))
    {
	tptype = TiGetTopType(tp);
	/* Scan top from right to left across range of tp */
	for (tp2 = RT(tile); RIGHT(tp2) > LEFT(tile); tp2 = BL(tp2))
	    if (TiGetBottomType(tp2) == tptype)
	    {
		/* Set range to length of overlap */
		if ((LEFT(tp2) <= RIGHT(tp)) && (LEFT(tp2) >= LEFT(tp)))
		{
		    area.r_xbot = LEFT(tp2) < LEFT(tile) ? LEFT(tile) : LEFT(tp2);
		    area.r_xtop = RIGHT(tp) > RIGHT(tile) ? RIGHT(tile) : RIGHT(tp);
		}
		else if ((RIGHT(tp2) >= LEFT(tp)) && (RIGHT(tp2) <= RIGHT(tp)))
		{
		    area.r_xbot = LEFT(tp) < LEFT(tile) ? LEFT(tile) : LEFT(tp);
		    area.r_xtop = RIGHT(tp2) > RIGHT(tile) ? RIGHT(tile) : RIGHT(tp2);
		}
		else continue;

		area.r_xbot *= cifScale;
		area.r_xtop *= cifScale;

		/* Does area violate minimum width requirement? */
		width = area.r_xtop - area.r_xbot;
		height = area.r_ytop - area.r_ybot;

		/* Manhattan requirement (to-do: Euclidean) */
		if (width < growDistance)
		{
		    locDist = (growDistance - width) / 2;
		    parea.r_xbot = area.r_xbot - locDist;
		    parea.r_xtop = area.r_xtop + locDist;
		}
		else
		{
		    parea.r_xbot = area.r_xbot;
		    parea.r_xtop = area.r_xtop;
		}
		if (height < growDistance)
		{
		    locDist = (growDistance - height) / 2;
		    parea.r_ybot = area.r_ybot - locDist;
		    parea.r_ytop = area.r_ytop + locDist;
		}
		else
		{
		    parea.r_ybot = area.r_ybot;
		    parea.r_ytop = area.r_ytop;
		}
		if ((width < growDistance) || (height < growDistance))
		{
    		    /* Ensure grid limit is not violated */
		    SetMinBoxGrid(&parea, growDistance);
		    DBPaintPlane(cifPlane, &parea, table, (PaintUndoInfo *) NULL);
		}
	    }
    }

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowGridFunc --
 *
 * 	Called for each relevant tile during grow-grid operations.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Scales the tile by cifScale, then expands its area by the
 *	remainder of the distance to the nearest grid point, as
 *	defined by the grid distance (growDistance) in the current
 *	CIFOp, then paints this area into cifNewPlane using the table
 *	passed as parameter.
 * ----------------------------------------------------------------------------
 */

int
cifGrowGridFunc(tile, table)
    Tile *tile;
    PaintResultType *table;		/* Table to be used for painting. */
{
    Rect area;
    int remainder;

    /* To be done---handle non-Manhattan geometry */
    TileType oldType = TiGetType(tile);

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot *= cifScale;
    if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot *= cifScale;
    if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop *= cifScale;
    if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop *= cifScale;

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot)
	area.r_xbot -= (abs(area.r_xbot) % growDistance);
    if (area.r_ybot > TiPlaneRect.r_ybot)
	area.r_ybot -= (abs(area.r_ybot) % growDistance);
    if (area.r_xtop < TiPlaneRect.r_xtop)
	area.r_xtop += (abs(area.r_xtop) % growDistance);
    if (area.r_ytop < TiPlaneRect.r_ytop)
	area.r_ytop += (abs(area.r_ytop) % growDistance);

    DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowEuclideanFunc --
 *
 * 	Called for each relevant tile during grow or shrink operations.
 *	For growing, these are solid tiles.  For shrinking, these are
 *	space tiles.   This routine differs from cifGrowFunc in that it
 *	grows the minimum distance on non-Manhattan edges necessary to
 *	create a euclidean distance to the edge of growDistance while
 *	keeping corner points on-grid.  This requires a substantially
 *	different algorithm from cifGrowFunc.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Scales the tile by cifScale, then expands its area by the
 *	distance in the current CIFOp, then paints this area into
 *	cifNewPlane using the table passed as parameter.
 * ----------------------------------------------------------------------------
 */

#define GROW_NORTH 0x1
#define GROW_SOUTH 0x2
#define GROW_EAST  0x4
#define GROW_WEST  0x8

#define STOP_NW 0x1	/*	   WN     EN	*/
#define STOP_SW 0x2	/*	NW +-------+ NE	*/
#define STOP_NE 0x4	/*	   |       |	*/
#define STOP_SE 0x8	/*	   |       |	*/
#define STOP_WN 0x10	/*      SW +-------+ SE	*/
#define STOP_WS 0x20	/*         WS     ES	*/
#define STOP_EN 0x40
#define STOP_ES 0x80

int
cifGrowEuclideanFunc(tile, table)
    Tile *tile;
    PaintResultType *table;		/* Table to be used for painting. */
{
    Tile *tp;
    Rect area, rtmp;
    TileType oldType = TiGetTypeExact(tile);
    unsigned char growDirs = GROW_NORTH | GROW_SOUTH | GROW_EAST | GROW_WEST;
    unsigned char cornerDirs = 0;

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot)
	area.r_xbot *= cifScale;
    else
	growDirs &= ~GROW_WEST;
    if (area.r_ybot > TiPlaneRect.r_ybot)
	area.r_ybot *= cifScale;
    else
	growDirs &= ~GROW_SOUTH;
    if (area.r_xtop < TiPlaneRect.r_xtop)
	area.r_xtop *= cifScale;
    else
	growDirs &= ~GROW_EAST;
    if (area.r_ytop < TiPlaneRect.r_ytop)
	area.r_ytop *= cifScale;
    else
	growDirs &= ~GROW_NORTH;

    /* Grow on diagonal tiles:  grow rectangular tiles around the	*/
    /* straight edges of the right-triangle, then copy the diagonal	*/
    /* tile (at its original size) in the direction of the diagonal.	*/
    /* Note:  A diagonal tile, by definition, can't have infinities.	*/

    if (oldType & TT_DIAGONAL)
    {
	int growDistanceX, growDistanceY;
	int height, width;
	double hyp;

	if (oldType & TT_SIDE)
	    growDirs &= ~GROW_WEST;
	else
	    growDirs &= ~GROW_EAST;

	if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION))
	    growDirs &= ~GROW_SOUTH;
	else
	    growDirs &= ~GROW_NORTH;

	/* Grow non-Manhattan edges to (the closest integer value	*/
	/* to) growDistance along the normal to the edge.  This	*/
	/* will overestimate the distance only to the minimum 	*/
	/* amount necessary to ensure on-grid endpoints.		*/

	width = area.r_xtop - area.r_xbot;
	height = area.r_ytop - area.r_ybot;
	hyp = sqrt((double)(width * width + height * height));
	growDistanceY = ceil((growDistance * (hyp - height)) / width);
	growDistanceX = ceil((growDistance * (hyp - width)) / height);

	/* Draw vertical tile to distance X */

	rtmp = area;
	if (!(growDirs & GROW_EAST))  rtmp.r_xtop = rtmp.r_xbot + growDistanceX;
	if (!(growDirs & GROW_WEST))  rtmp.r_xbot = rtmp.r_xtop - growDistanceX;
	if (!(growDirs & GROW_SOUTH)) rtmp.r_ybot -=growDistance;
	if (!(growDirs & GROW_NORTH)) rtmp.r_ytop += growDistance;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

	/* Draw horizontal tile to distance Y */

	rtmp = area;
	if (!(growDirs & GROW_EAST))  rtmp.r_xtop += growDistance;
	if (!(growDirs & GROW_WEST))  rtmp.r_xbot -= growDistance;
	if (!(growDirs & GROW_SOUTH)) rtmp.r_ybot = rtmp.r_ytop - growDistanceY;
	if (!(growDirs & GROW_NORTH)) rtmp.r_ytop = rtmp.r_ybot + growDistanceY;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

	/* Finally:  translate, resize, and paint the diagonal tile */

	rtmp = area;

	if (!(growDirs & GROW_NORTH))
	    rtmp.r_ytop += growDistance;
	else
	    rtmp.r_ytop -= growDistanceY;
	if (!(growDirs & GROW_SOUTH))
	    rtmp.r_ybot -= growDistance;
	else
	    rtmp.r_ybot += growDistanceY;
	if (!(growDirs & GROW_EAST))
	    rtmp.r_xtop += growDistance;
	else
	    rtmp.r_xtop -= growDistanceX;
	if (!(growDirs & GROW_WEST))
	    rtmp.r_xbot -= growDistance;
	else
	    rtmp.r_xbot += growDistanceX;

	DBNMPaintPlane(cifPlane, oldType, &rtmp, table, (PaintUndoInfo *) NULL);
	oldType = (growDirs & GROW_EAST) ? TiGetRightType(tile) : TiGetLeftType(tile);
    }
    else
	DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);

    /* Check tile corner areas for paint */

    tp = TR(tile);
    if (TiGetLeftType(tp) == oldType) cornerDirs |= STOP_NE;
    for (; TOP(LB(tp)) > BOTTOM(tile); tp = LB(tp));
    if (TiGetLeftType(tp) == oldType) cornerDirs |= STOP_SE;

    tp = RT(tile);
    if (TiGetBottomType(tp) == oldType) cornerDirs |= STOP_EN;
    for (; RIGHT(BL(tp)) > LEFT(tile); tp = BL(tp));
    if (TiGetBottomType(tp) == oldType) cornerDirs |= STOP_WN;

    tp = BL(tile);
    if (TiGetRightType(tp) == oldType) cornerDirs |= STOP_SW;
    for (; BOTTOM(RT(tp)) < TOP(tile); tp = RT(tp));
    if (TiGetRightType(tp) == oldType) cornerDirs |= STOP_NW;

    tp = LB(tile);
    if (TiGetTopType(tp) == oldType) cornerDirs |= STOP_WS;
    for (; LEFT(TR(tp)) < RIGHT(tile); tp = TR(tp));
    if (TiGetTopType(tp) == oldType) cornerDirs |= STOP_ES;

    if (growDirs & GROW_NORTH)
    {
	rtmp = area;
	rtmp.r_ybot = area.r_ytop;
	rtmp.r_ytop = area.r_ytop + growDistance;
	if ((cornerDirs & (STOP_EN | STOP_NE)) == 0)
	    if (growDirs & GROW_EAST) rtmp.r_xtop += growDistance;
	if ((cornerDirs & (STOP_WN | STOP_NW)) == 0)
	    if (growDirs & GROW_WEST) rtmp.r_xbot -= growDistance;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_EAST)
    {
	rtmp = area;
	rtmp.r_xbot = area.r_xtop;
	rtmp.r_xtop = area.r_xtop + growDistance;
	if ((cornerDirs & (STOP_EN | STOP_NE)) == 0)
	    if (growDirs & GROW_NORTH) rtmp.r_ytop += growDistance;
	if ((cornerDirs & (STOP_SE | STOP_ES)) == 0)
	    if (growDirs & GROW_SOUTH) rtmp.r_ybot -= growDistance;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_SOUTH)
    {
	rtmp = area;
	rtmp.r_ytop = area.r_ybot;
	rtmp.r_ybot = area.r_ybot - growDistance;
	if ((cornerDirs & (STOP_SE | STOP_ES)) == 0)
	    if (growDirs & GROW_EAST) rtmp.r_xtop += growDistance;
	if ((cornerDirs & (STOP_SW | STOP_WS)) == 0)
	    if (growDirs & GROW_WEST) rtmp.r_xbot -= growDistance;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    if (growDirs & GROW_WEST)
    {
	rtmp = area;
	rtmp.r_xtop = area.r_xbot;
	rtmp.r_xbot = area.r_xbot - growDistance;
	if ((cornerDirs & (STOP_NW | STOP_WN)) == 0)
	    if (growDirs & GROW_NORTH) rtmp.r_ytop += growDistance;
	if ((cornerDirs & (STOP_SW | STOP_WS)) == 0)
	    if (growDirs & GROW_SOUTH) rtmp.r_ybot -= growDistance;
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);
    }

    CIFTileOps++;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGrowFunc --
 *
 * 	Called for each relevant tile during grow or shrink operations.
 *	For growing, these are solid tiles.  For shrinking, these are
 *	space tiles.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Scales the tile by cifScale, then expands its area by the
 *	distance in the current CIFOp, then paints this area into
 *	cifNewPlane using the table passed as parameter.
 * ----------------------------------------------------------------------------
 */

int
cifGrowFunc(tile, table)
    Tile *tile;
    PaintResultType *table;		/* Table to be used for painting. */
{
    Rect area;
    TileType oldType = TiGetTypeExact(tile);

    TiToRect(tile, &area);

    /* In scaling the tile, watch out for infinities!!  If something
     * is already infinity, don't change it. */

    if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot *= cifScale;
    if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot *= cifScale;
    if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop *= cifScale;
    if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop *= cifScale;

    /* Grow on diagonal tiles:  grow rectangular tiles around the	*/
    /* straight edges of the right-triangle, then copy the diagonal	*/
    /* tile (at its original size) in the direction of the diagonal.	*/
    /* Note:  A diagonal tile, by definition, can't have infinities.	*/

    if (oldType & TT_DIAGONAL)
    {
	Rect rtmp;

	/* Grow top and bottom */

	rtmp.r_ybot = area.r_ybot - growDistance;
	rtmp.r_ytop = area.r_ytop + growDistance;

	/* Grow around left or right edge */

	if (oldType & TT_SIDE)
	{
	    rtmp.r_xbot = area.r_xtop - growDistance;
	    rtmp.r_xtop = area.r_xtop + growDistance;
	}
	else
	{
	    rtmp.r_xbot = area.r_xbot - growDistance;
	    rtmp.r_xtop = area.r_xbot + growDistance;
	}
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

	/* Now do the same for the other edge. */

	rtmp.r_xbot = area.r_xbot - growDistance;
	rtmp.r_xtop = area.r_xtop + growDistance;

	if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
	{
	    rtmp.r_ybot = area.r_ytop - growDistance;
	    rtmp.r_ytop = area.r_ytop + growDistance;
	}
	else /* bottom */
	{
	    rtmp.r_ybot = area.r_ybot - growDistance;
	    rtmp.r_ytop = area.r_ybot + growDistance;
	}
	DBPaintPlane(cifPlane, &rtmp, table, (PaintUndoInfo *) NULL);

	/* Finally, Move and replace the diagonal tile */

	if (oldType & TT_SIDE)
	{
	    rtmp.r_xtop = area.r_xtop - growDistance;
	    rtmp.r_xbot = area.r_xbot - growDistance;
	}
	else
	{
	    rtmp.r_xtop = area.r_xtop + growDistance;
	    rtmp.r_xbot = area.r_xbot + growDistance;
	}

	if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
	{
	    rtmp.r_ytop = area.r_ytop - growDistance;
	    rtmp.r_ybot = area.r_ybot - growDistance;
	}
	else	/* bottom */
	{
	    rtmp.r_ytop = area.r_ytop + growDistance;
	    rtmp.r_ybot = area.r_ybot + growDistance;
	}
	DBNMPaintPlane(cifPlane, oldType, &rtmp, table, (PaintUndoInfo *) NULL);
    }
    else
    {

	/* In scaling the tile, watch out for infinities!!  If something
	 * is already infinity, don't change it. */

	if (area.r_xbot > TiPlaneRect.r_xbot) area.r_xbot -= growDistance;
	if (area.r_ybot > TiPlaneRect.r_ybot) area.r_ybot -= growDistance;
	if (area.r_xtop < TiPlaneRect.r_xtop) area.r_xtop += growDistance;
	if (area.r_ytop < TiPlaneRect.r_ytop) area.r_ytop += growDistance;

	DBPaintPlane(cifPlane, &area, table, (PaintUndoInfo *) NULL);
    }

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatFunc --
 *
 * 	Called once for each tile to be selectively bloated.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Uses the bloat table in the current CIFOp to expand the
 *	tile depending on which tiles it abuts, then paints the
 *	expanded area into the new CIF plane.  The bloat table
 *	contains one entry for each tile type.  When that tile
 *	type is seen next to the current tile, the area of the current
 *	tile is bloated by the table value in that location.  The
 *	only exception to this rule is that internal edges (between
 *	two tiles of the same type) cause no bloating.
 *	Note:  the original tile is scaled into CIF coordinates.
 * ----------------------------------------------------------------------------
 */

int
cifBloatFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;
{
    Rect tileArea, cifArea, bloat;
    TileType oldType, type, topLeftType, bottomRightType;
    Tile *t;
    int tilestart, tilestop, cifstart, cifstop;
    BloatData *bloats = (BloatData *)clientData;
    int *bloatTable = (int *)bloats->bl_distance;

    oldType = TiGetTypeExact(tile);
    TiToRect(tile, &tileArea);

    /* Output the original area of the tile. */

    cifArea = tileArea;
    cifArea.r_xbot *= cifScale;
    cifArea.r_xtop *= cifScale;
    cifArea.r_ybot *= cifScale;
    cifArea.r_ytop *= cifScale;

    /* This is a modified version of the nonmanhattan grow function.	*/
    /* We grow only in the direction of the diagonal.			*/
    /* This will not work in all situations!  Corner extensions are not	*/
    /* considered (but should be, for completeness).			*/

    if (oldType & TT_DIAGONAL)
    {
	TileType otherType = (oldType & TT_SIDE) ?
		TiGetLeftType(tile) : TiGetRightType(tile);
	int dist = bloatTable[otherType];

	/* The Euclidean grow function is identical to Euclidean bloat-or */
	if (CIFCurStyle->cs_flags & CWF_GROW_EUCLIDEAN)
	{
	    growDistance = dist;
	    cifGrowEuclideanFunc(tile, CIFPaintTable);
	}
	else
	{

	    /* Grow top and bottom */

	    if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
	    {
		bloat.r_ybot = cifArea.r_ytop - dist;
		bloat.r_ytop = cifArea.r_ytop;
	    }
	    else /* bottom */
	    {
		bloat.r_ybot = cifArea.r_ybot;
		bloat.r_ytop = cifArea.r_ybot + dist;
	    }

	    /* Grow around left or right edge */

	    if (oldType & TT_SIDE)
	    {
		bloat.r_xbot = cifArea.r_xbot - dist;
		bloat.r_xtop = cifArea.r_xtop;
	    }
	    else
	    {
		bloat.r_xbot = cifArea.r_xbot;
		bloat.r_xtop = cifArea.r_xtop + dist;
	    }
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable, (PaintUndoInfo *) NULL);

	    /* Now do the same for the left or right edge. */

	    if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
	    {
		bloat.r_ybot = cifArea.r_ybot - dist;
		bloat.r_ytop = cifArea.r_ytop;
	    }
	    else /* bottom */
	    {
		bloat.r_ybot = cifArea.r_ybot;
		bloat.r_ytop = cifArea.r_ytop + dist;
	    }

	    if (oldType & TT_SIDE)
	    {
		bloat.r_xbot = cifArea.r_xtop - dist;
		bloat.r_xtop = cifArea.r_xtop;
	    }
	    else
	    {
		bloat.r_xbot = cifArea.r_xbot;
		bloat.r_xtop = cifArea.r_xbot + dist;
	    }
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable, (PaintUndoInfo *) NULL);

	    /* Finally, Move and replace the diagonal tile */

	    if (oldType & TT_SIDE)
	    {
		bloat.r_xtop = cifArea.r_xtop - dist;
		bloat.r_xbot = cifArea.r_xbot - dist;
	    }
	    else
	    {
		bloat.r_xtop = cifArea.r_xtop + dist;
		bloat.r_xbot = cifArea.r_xbot + dist;
	    }

	    if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION)) /* top */
	    {
		bloat.r_ytop = cifArea.r_ytop - dist;
		bloat.r_ybot = cifArea.r_ybot - dist;
	    }
	    else	/* bottom */
	    {
		bloat.r_ytop = cifArea.r_ytop + dist;
		bloat.r_ybot = cifArea.r_ybot + dist;
	    }
	    DBNMPaintPlane(cifPlane, oldType, &bloat, CIFPaintTable,
			(PaintUndoInfo *) NULL);
	}
    }
    else
	DBNMPaintPlane(cifPlane, oldType, &cifArea, CIFPaintTable,
			(PaintUndoInfo *) NULL);

    /* Go around the tile, scanning the neighbors along each side.
     * Start with the left side, and output the bloats along that
     * side, if any.
     */

    tilestop = tileArea.r_ytop;
    cifstop = cifArea.r_ytop;
    type = oldType;

    /* If the tile type doesn't exist on the left side, skip */
    if (oldType & TT_DIAGONAL)
    {
	type = TiGetLeftType(tile);
	if (oldType & TT_SIDE)
	{
	    if (oldType & TT_DIRECTION)
	    {
		topLeftType = type;
		goto dotop;
	    }
	    else
	    {
		tilestop = tileArea.r_ybot;
		cifstop = cifArea.r_ybot;
		type = TiGetBottomType(tile);
	    }
	}
    }

    bloat.r_ybot = cifArea.r_ybot - bloatTable[TiGetRightType(LB(tile))];
    bloat.r_xtop = cifArea.r_xbot;
    for (t = BL(tile); BOTTOM(t) < TOP(tile); t = RT(t))
    {
	if (BOTTOM(t) >= tilestop) continue;
	topLeftType = TiGetRightType(t);
	bloat.r_xbot = bloat.r_xtop - bloatTable[topLeftType];
	if (TOP(t) > tilestop)
	    bloat.r_ytop = cifstop;
	else bloat.r_ytop = cifScale * TOP(t);
	if ((bloatTable[topLeftType] != 0) && (topLeftType != type))
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
		(PaintUndoInfo *) NULL);
	bloat.r_ybot = bloat.r_ytop;
    }

    /* Now do the top side.  Use the type of the top-left tile to
     * side-extend the left end of the top bloat in order to match
     * things up at the corner.
     */

dotop:
    cifstart = cifArea.r_xtop;
    tilestart = tileArea.r_xtop;

    /* If the tile type doesn't exist on the top side, skip */
    if (oldType & TT_DIAGONAL)
    {
	type = TiGetTopType(tile);
	if (((oldType & TT_SIDE) >> 1) != (oldType & TT_DIRECTION))
	{
	    if (oldType & TT_SIDE)
		goto doright;
	    else
	    {
		cifstart = cifArea.r_xbot;
		tilestart = tileArea.r_xbot;
		type = TiGetLeftType(tile);
	    }
	}
    }

    bloat.r_ybot = cifArea.r_ytop;
    bloat.r_xtop = cifstart;
    for (t = RT(tile); RIGHT(t) > LEFT(tile); t = BL(t))
    {
	TileType otherType;
	if (LEFT(t) >= tilestart) continue;
	otherType = TiGetBottomType(t);
	bloat.r_ytop = bloat.r_ybot + bloatTable[otherType];
	if (LEFT(t) <= tileArea.r_xbot)
	    bloat.r_xbot = cifArea.r_xbot - bloatTable[topLeftType];
	else bloat.r_xbot = cifScale * LEFT(t);
	if ((bloatTable[otherType] != 0) && (otherType != type))
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
		(PaintUndoInfo *) NULL);
	bloat.r_xtop = bloat.r_xbot;
    }

    /* Now do the right side. */

doright:
    tilestop = tileArea.r_ybot;
    cifstop = cifArea.r_ybot;

    /* If the tile type doesn't exist on the right side, skip */
    if (oldType & TT_DIAGONAL)
    {
	type = TiGetRightType(tile);
	if (!(oldType & TT_SIDE))
	{
	    if (oldType & TT_DIRECTION)
	    {
		bottomRightType = type;
		goto dobottom;
	    }
	    else
	    {
		tilestop = tileArea.r_ytop;
		cifstop = cifArea.r_ytop;
		type = TiGetTopType(tile);
	    }
	}
    }

    bloat.r_ytop = cifArea.r_ytop + bloatTable[TiGetLeftType(RT(tile))];
    bloat.r_xbot = cifArea.r_xtop;
    for (t = TR(tile); TOP(t) > BOTTOM(tile); t = LB(t))
    {
	if (TOP(t) <= tilestop) continue;
	bottomRightType = TiGetLeftType(t);
	bloat.r_xtop = bloat.r_xbot + bloatTable[bottomRightType];
	if (BOTTOM(t) < tilestop)
	    bloat.r_ybot = cifstop;
	else bloat.r_ybot = cifScale * BOTTOM(t);
	if ((bloatTable[bottomRightType] != 0) && (bottomRightType != type))
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
		(PaintUndoInfo *) NULL);
	bloat.r_ytop = bloat.r_ybot;
    }

    /* Now do the bottom side.  Use the type of the bottom-right tile
     * to side-extend the right end of the bottom bloat in order to match
     * things up at the corner.
     */

dobottom:
    cifstart = cifArea.r_xbot;
    tilestart = tileArea.r_xbot;

    /* If the tile type doesn't exist on the bottom side, skip */
    if (oldType & TT_DIAGONAL)
    {
	type = TiGetBottomType(tile);
	if (((oldType & TT_SIDE) >> 1) == (oldType & TT_DIRECTION))
	{
	    if (!(oldType & TT_DIRECTION))
		goto endbloat;
	    else
	    {
		cifstart = cifArea.r_xtop;
		tilestart = tileArea.r_xtop;
		type = TiGetRightType(tile);
	    }
	}
    }

    bloat.r_ytop = cifArea.r_ybot;
    bloat.r_xbot = cifstart;
    for (t = LB(tile); LEFT(t) < RIGHT(tile); t = TR(t))
    {
	TileType otherType;
	if (RIGHT(t) <= tilestart) continue;
	otherType = TiGetTopType(t);
	bloat.r_ybot = bloat.r_ytop - bloatTable[otherType];
	if (RIGHT(t) >= tileArea.r_xtop)
	    bloat.r_xtop = cifArea.r_xtop + bloatTable[bottomRightType];
	else bloat.r_xtop = cifScale * RIGHT(t);
	if ((bloatTable[otherType] != 0) && (otherType != type))
	    DBPaintPlane(cifPlane, &bloat, CIFPaintTable,
		(PaintUndoInfo *) NULL);
	bloat.r_xbot = bloat.r_xtop;
    }

endbloat:
    CIFTileOps += 1;
    return 0;
}

#define CIF_PENDING     0
#define CIF_UNPROCESSED CLIENTDEFAULT
#define CIF_PROCESSED   1
#define CIF_IGNORE   	2

#define PUSHTILE(tp, stack) \
    if ((tp)->ti_client == (ClientData) CIF_UNPROCESSED) { \
	(tp)->ti_client = (ClientData) CIF_PENDING; \
	STACKPUSH((ClientData) (tp), stack); \
    }

/*
 *-------------------------------------------------------
 *
 * cifProcessResetFunc --
 *
 *	Unmark tiles
 *
 * Results:	Return 0 to keep the search going.
 *
 *-------------------------------------------------------
 */

int
cifProcessResetFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;	/* unused */
{
    tile->ti_client = (ClientData) CIF_UNPROCESSED;
    return 0;
}

/*
 *-------------------------------------------------------
 *
 * cifFoundFunc --
 *
 *	Find the first tile in the given area.
 *
 * Results:
 *	Return 1 to stop the search and process.
 *	Set clientData to the tile found.
 *
 *-------------------------------------------------------
 */

int
cifFoundFunc(tile, BloatStackPtr)
    Tile *tile;
    Stack **BloatStackPtr;
{
    PUSHTILE(tile, *BloatStackPtr);
    return 0;
}

/* Data structure for bloat-all function */
typedef struct _bloatStruct {
    CIFOp	*op;
    CellDef	*def;
    TileTypeBitMask connect;
    Plane       **temps;
} BloatStruct;

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatAllFunc --
 *
 * 	Called once for each tile to be selectively bloated
 *	using the CIFOP_BLOATALL operation.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Uses the bloat table in the current CIFOp to expand the tile,
 *	depending on which tiles it abuts.  All bordering material that
 *	has bl_distance = 1 is painted into the result plane.
 *
 * ----------------------------------------------------------------------------
 */

int
cifBloatAllFunc(tile, bls)
    Tile *tile;			/* The tile to be processed. */
    BloatStruct *bls;
{
    Rect area;
    TileTypeBitMask *connect;
    Tile *t, *tp;
    TileType type, ttype;
    BloatData *bloats;
    int i, locScale;
    PlaneMask pmask;
    CIFOp *op;
    CellDef *def;
    Plane **temps;
    static Stack *BloatStack = (Stack *)NULL;

    op = bls->op;
    def = bls->def;
    temps = bls->temps;
    connect = &bls->connect;
    bloats = (BloatData *)op->co_client;

    /* This search function is based on drcCheckArea */

    if (BloatStack == (Stack *)NULL)
	BloatStack = StackNew(64);

    /* If the type of the tile to be processed is not in the same plane	*/
    /* as the bloat type(s), then find any tile under the tile to be	*/
    /* processed that belongs to the connect mask, and use that as the	*/
    /* starting tile.							*/

    t = tile;
    type = TiGetType(tile);
    if (type == CIF_SOLIDTYPE)
    {
	pmask = 0;
	if (bloats->bl_plane < 0)   /* Bloat types are CIF types */
	    locScale = 1;
	else
	    locScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;

	/* Get the tile into magic database coordinates if it's in CIF coords */
	TiToRect(tile, &area);
	area.r_xbot /= locScale;
	area.r_xtop /= locScale;
	area.r_ybot /= locScale;
	area.r_ytop /= locScale;
    }
    else
    {
	int pNum = DBPlane(type);
	pmask = (bloats->bl_plane < 0) ? 0 :
		CoincidentPlanes(connect, PlaneNumToMaskBit(pNum));
	if (pmask == 0) TiToRect(tile, &area);
	if (bloats->bl_plane < 0)
	{
	    /* Get the tile into CIF database coordinates if it's in magic coords */
	    area.r_xbot *= cifScale;
	    area.r_xtop *= cifScale;
	    area.r_ybot *= cifScale;
	    area.r_ytop *= cifScale;
	    locScale = 1;
	}
	else
	{
	    locScale = cifScale;
	}
    }
    if (pmask == 0)
    {
	if (bloats->bl_plane < 0)   /* Bloat types are CIF types */
	{
	    /* This expands the area to the OR of all temp layers specified */
	    /* which may or may not be useful;  normally one would expand   */
	    /* into a single layer if a temp layer is specified.	    */

	    for (ttype = 0; ttype < TT_MAXTYPES; ttype++, temps++)
		if (bloats->bl_distance[ttype] > 0)
		    (void) DBSrPaintArea((Tile *)NULL, *temps, &area,
				&CIFSolidBits, cifFoundFunc, (ClientData)(&BloatStack));
	}
	else
	    DBSrPaintArea((Tile *)NULL, def->cd_planes[bloats->bl_plane], &area,
		    connect, cifFoundFunc, (ClientData)(&BloatStack));
    }
    else
	PUSHTILE(t, BloatStack);

    while (!StackEmpty(BloatStack))
    {
	t = (Tile *) STACKPOP(BloatStack);
	if (t->ti_client != (ClientData)CIF_PENDING) continue;
        t->ti_client = (ClientData)CIF_PROCESSED;

	/* Get the tile into CIF coordinates. */

	TiToRect(t, &area);
	area.r_xbot *= locScale;
	area.r_ybot *= locScale;
	area.r_xtop *= locScale;
	area.r_ytop *= locScale;

	DBNMPaintPlane(cifPlane, TiGetTypeExact(t), &area,
		CIFPaintTable, (PaintUndoInfo *) NULL);

	/* Top */
	for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
	    if (TTMaskHasType(connect, TiGetBottomType(tp)))
		PUSHTILE(tp, BloatStack);

	/* Left */
	for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
	    if (TTMaskHasType(connect, TiGetRightType(tp)))
		PUSHTILE(tp, BloatStack);

	/* Bottom */
	for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
	    if (TTMaskHasType(connect, TiGetTopType(tp)))
		PUSHTILE(tp, BloatStack);

	/* Right */
	for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
	    if (TTMaskHasType(connect, TiGetLeftType(tp)))
		PUSHTILE(tp, BloatStack);
    }

    /* Clear the tiles that were processed */

    tile->ti_client = (ClientData)CIF_UNPROCESSED;
    STACKPUSH(tile, BloatStack);
    while (!StackEmpty(BloatStack))
    {
	t = (Tile *) STACKPOP(BloatStack);

	/* Top */
	for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
	    if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
	    {
		tp->ti_client = (ClientData)CIF_UNPROCESSED;
		STACKPUSH(tp, BloatStack);
	    }

	/* Left */
	for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
	    if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
	    {
		tp->ti_client = (ClientData)CIF_UNPROCESSED;
		STACKPUSH(tp, BloatStack);
	    }

	/* Bottom */
	for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
	    if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
	    {
		tp->ti_client = (ClientData)CIF_UNPROCESSED;
		STACKPUSH(tp, BloatStack);
	    }

	/* Right */
	for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
	    if (tp->ti_client != (ClientData)CIF_UNPROCESSED)
	    {
		tp->ti_client = (ClientData)CIF_UNPROCESSED;
		STACKPUSH(tp, BloatStack);
	    }
    }

    return 0;	/* Keep the search alive. . . */
}

/* Data structure to pass plane and minimum width to the callback function */
typedef struct _bridgeStruct {
    Plane       *plane;
    BridgeData	*bridge;
} BridgeStruct;

/* Bridge Check data structure */
typedef struct _bridgeCheckStruct {
   Tile *tile;		/* Tile that triggered search (ignore this tile) */
   Rect *area;		/* Area of search */
   int	direction;	/* What outside corner to look for */
   Tile *violator;	/* Return the violator tile in this space */
   TileType checktype;	/* Type to check for, either TT_SPACE or CIF_SOLIDTYPE */
} BridgeCheckStruct;

/* Direction flags */
#define BRIDGE_NW	1
#define BRIDGE_SW	2

/*
 * ----------------------------------------------------------------------------
 *
 * Function that returns the Euclidean distance corresponding to a manhattan
 * distance of the given width, at 45 degrees.
 *
 * This is used by the bridging method to keep the amount of extra material
 * added to a minimum.
 *
 * ----------------------------------------------------------------------------
 */

int
GetEuclideanWidthGrid(width)
    int width;
{
    int weuclid;
    int delta;
    int limit;

    limit = CIFCurStyle->cs_gridLimit * CIFCurStyle->cs_expander;
    limit /= (CIFCurStyle->cs_flags & CWF_ANGSTROMS) ? 100 : 10;

    weuclid = (int)(ceil((double)width * 0.70711));
    if (CIFCurStyle && (limit > 1))
    {
	delta = weuclid % limit;
	if (delta > 0)
	{
	    weuclid -= delta;
	    weuclid += limit;
	}
    }
    return weuclid;
}

/*
 * ----------------------------------------------------------------------------
 *
 * GetExpandedAreaGrid --
 *
 *	Given a pointer "area" to a Rect and a minimum layer width "width",
 *	find the minimum size rectangle that expands "area" in all directions
 *	equally to ensure that the length of the diagonal of the expanded
 *	area is greater than or equal to "width".  This is used by the
 *	"bridge" operator to ensure that the bridging rectangle meets the
 *	minimum layer width requirement.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The Rect structure pointed to by "area" may be altered.
 *
 * Notes:
 *	The calculation needed depends on the geometry.  If there is a
 *	horizontal gap between the tiles, then the bridging shape must
 *	be as tall as the minimum width rule;  this is the vertical
 *	case (horiz = FALSE).  If there is a vertical gap between the
 *	tiles, then the bridging shape must be as wide as the minimum
 *	width rule;  this is the horizontal case (horiz = TRUE).  Then
 *	calculate the length of the bridging shape in the other direction
 *	needed to ensure that the join of the bridging shape and the
 *	preexisting shapes is always wide enough to satisfy the width
 *	rule.  Which calculation is needed depends on whether the shapes
 *	are catecorner (overlap = FALSE) or overlapping in one direction
 *	(overlap = TRUE).
 *
 * ----------------------------------------------------------------------------
 */

void
GetExpandedAreaGrid(wrule, space, area)
    int wrule;
    bool space;
    Rect *area;
{
    bool horiz;
    bool overlap;
    Rect r;

    int width, height, dx, dy, a, b, delta, dx2, dy2, limit;

    overlap = FALSE;
    if (area->r_xbot > area->r_xtop)
    {
	overlap = TRUE;
	horiz = (space) ? FALSE : TRUE;
    }
    if (area->r_ybot > area->r_ytop)
    {
	overlap = TRUE;
	horiz = (space) ? TRUE : FALSE;
    }

    GeoCanonicalRect(area, &r);
    width = r.r_xtop - r.r_xbot;
    height = r.r_ytop - r.r_ybot;

    if (overlap == FALSE)
	horiz = (width > height);

    if (horiz)
    {
	a = wrule - width;
	dx = (int)ceilf((float)a / 2.0);
	if (overlap || space)
	    b = wrule * wrule - (width + dx) * (width + dx);
	else
	    b = wrule * wrule - dx * dx;
	if (space && !overlap)
	    dy = (int)ceilf(sqrtf((float)b) - height);
	else
	    dy = (int)ceilf(sqrtf((float)b));

	b = wrule * wrule - width * width;
	dy2 = (int)ceilf((sqrtf((float)b) - height) / 2.0);
	if (dy2 > dy) dy = dy2;
    }
    else
    {
	a = wrule - height;
	dy = (int)ceilf((float)a / 2.0);
	if (overlap || space)
	    b = wrule * wrule - (height + dy) * (height + dy);
	else
	    b = wrule * wrule - dy * dy;
	if (space && !overlap)
	    dx = (int)ceilf(sqrtf((float)b) - width);
	else
	    dx = (int)ceilf(sqrtf((float)b));

	b = wrule * wrule - height * height;
	dx2 = (int)ceilf((sqrtf((float)b) - width) / 2.0);
	if (dx2 > dx) dx = dx2;
    }

    r.r_xbot -= dx;
    r.r_xtop += dx;
    r.r_ybot -= dy;
    r.r_ytop += dy;

    limit = CIFCurStyle->cs_gridLimit * CIFCurStyle->cs_expander;
    limit /= (CIFCurStyle->cs_flags & CWF_ANGSTROMS) ? 100 : 10;

    if (CIFCurStyle && (limit > 1))
    {
	delta = r.r_xbot % limit;
	if (delta > 0)
	    r.r_xbot -= delta;
	else if (delta < 0)
	    r.r_xbot -= limit + delta;

	delta = r.r_xtop % limit;
	if (delta > 0)
	    r.r_xtop += limit - delta;
	else if (delta < 0)
	    r.r_xtop -= delta;

	delta = r.r_ybot % limit;
	if (delta > 0)
	    r.r_ybot -= delta;
	else if (delta < 0)
	    r.r_ybot -= limit + delta;

	delta = r.r_ytop % limit;
	if (delta > 0)
	    r.r_ytop += limit - delta;
	else if (delta < 0)
	    r.r_ytop -= delta;
    }

    *area = r;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBridgeFunc1 --
 *
 * 	Called for each relevant tile during bridge operations.  The
 *	bridge operation is responsible for preventing a grow-shrink
 *	pair of operations from leaving width or spacing DRC errors,
 *	which happens when tiles are in a catecorner position from
 *	each other.  The bridge operation adds a bridge of material
 *	between the two tiles that solves spacing requirements between
 *      the two tiles while satisfying the minimum width requirements,
 *	adding a minimum amount of material to do so.
 *
 *	The current version of this routine adds material on a stair-step
 *	pattern;  preferably this should be extended to create material
 *	at allowed angles, where the allowed angles (90, 45, or any) are
 *	specified as an option to the bridge statement in the tech file.
 *
 *	GrowDistance is equal to the spacing rule distance needing to be
 *	satisfied.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Paints into cifNewPlane.  Tiles in old plane are tagged with
 *	a static value in ClientData, which does not need to be reset
 *	since the old plane will be free'd.
 * ----------------------------------------------------------------------------
 */

int
cifBridgeFunc1(tile, brs)
    Tile *tile;
    BridgeStruct *brs;
{
    Plane *plane = brs->plane;
    Rect area;
    Tile *tp1, *tp2, *tpx;
    int width = brs->bridge->br_width;
    int spacing = growDistance;
    BridgeCheckStruct brcs;
    int cifBridgeCheckFunc();	/* Forward reference */

    /* If tile is marked, then it has been handled, so ignore it */
    if (tile->ti_client != (ClientData)CIF_UNPROCESSED) return 0;

    /* Find each tile outside corner (only two cases need to be checked) */

    /* Check for NE outside corner */
    tp1 = TR(tile);  /* Tile on right side at the top of this tile */
    tp2 = RT(tile);  /* Tile on top side at the right of this tile */
    if ((TiGetLeftType(tp1) == TT_SPACE) &&
	    (TiGetBottomType(tp2) == TT_SPACE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile) - width;
	area.r_xtop = RIGHT(tile) + spacing;
	area.r_ybot = TOP(tile) - width;
	area.r_ytop = TOP(tile) + spacing;

	/* Find violator tiles */
	brcs.tile = tile;
	brcs.area = &area;
	brcs.direction = BRIDGE_SW;
	brcs.checktype = TT_SPACE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &CIFSolidBits, cifBridgeCheckFunc, (ClientData)&brcs) == 1)
	{
	    tpx = brcs.violator;

	    area.r_xbot = RIGHT(tile);
	    area.r_ybot = TOP(tile);
	    area.r_xtop = LEFT(tpx);
	    area.r_ytop = BOTTOM(tpx);

 	    GetExpandedAreaGrid(width, FALSE, &area);

	    /* Trivial implementation: fill box */
	    /* (to do: use stairstep to avoid filling unnecessary areas) */
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	}
    }

    /* Check for SE outside corner */
    for (tp1 = TR(tile); BOTTOM(tp1) > BOTTOM(tile); tp1 = LB(tp1));
    for (tp2 = LB(tile); RIGHT(tp1) < RIGHT(tile); tp2 = TR(tp2));
    if ((TiGetLeftType(tp1) == TT_SPACE) &&
	    (TiGetTopType(tp2) == TT_SPACE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile) - width;
	area.r_xtop = RIGHT(tile) + spacing;
	area.r_ybot = BOTTOM(tile) - spacing;
	area.r_ytop = BOTTOM(tile) + width;

	/* Find violator tiles */
	brcs.tile = tile;
	brcs.area = &area;
	brcs.direction = BRIDGE_NW;
	brcs.checktype = TT_SPACE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &CIFSolidBits, cifBridgeCheckFunc, (ClientData)&brcs) == 1)
	{
	    tpx = brcs.violator;

	    area.r_xbot = RIGHT(tile);
	    area.r_ybot = TOP(tpx);
	    area.r_xtop = LEFT(tpx);
	    area.r_ytop = BOTTOM(tile);

 	    GetExpandedAreaGrid(width, FALSE, &area);

	    /* Trivial implementation: fill box */
	    /* (to do: use stairstep to avoid filling unnecessary areas) */
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	}
    }
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 * SetMinBoxGrid ---
 *
 *	Adjust the given area by expanding evenly on both sides so that it
 *	has a width and heigth no less than the given width.  Then further
 *	expand the box to ensure that it falls on the CIF minimum grid.
 *
 *  Returns:  Nothing
 *
 *  Side Effects:  Point to Rect "area" may be modified.
 *
 * ----------------------------------------------------------------------------
 */

void
SetMinBoxGrid(area, width)
    Rect *area;
    int width;
{
    int wtest;
    int wtot;
    int delta;
    int limit;

    wtest = (area->r_xtop - area->r_xbot);
    wtot = area->r_xtop + area->r_xbot;
    if (wtest < width)
    {
	area->r_xbot = (wtot - width) / 2;
	area->r_xtop = (wtot + width) / 2;
    }
    wtest = (area->r_ytop - area->r_ybot);
    wtot = area->r_ytop + area->r_ybot;
    if (wtest < width)
    {
	area->r_ybot = (wtot - width) / 2;
	area->r_ytop = (wtot + width) / 2;
    }

    limit = CIFCurStyle->cs_gridLimit * CIFCurStyle->cs_expander;
    limit /= (CIFCurStyle->cs_flags & CWF_ANGSTROMS) ? 100 : 10;

    if (CIFCurStyle && (limit > 1))
    {
	delta = abs(area->r_xbot) % limit;
	if (delta > 0)
	{
	    if (area->r_xbot < 0)
	    {
		area->r_xbot += delta;
		area->r_xbot -= limit;
	    }
	    else
		area->r_xbot -= delta;
	}

	delta = abs(area->r_xtop) % limit;
	if (delta > 0)
	{
	    if (area->r_xtop < 0)
		area->r_xtop += delta;
	    else
	    {
		area->r_xtop -= delta;
		area->r_xtop += limit;
	    }
	}

	delta = abs(area->r_ybot) % limit;
	if (delta > 0)
	{
	    if (area->r_ybot < 0)
	    {
		area->r_ybot += delta;
		area->r_ybot -= limit;
	    }
	    else
		area->r_ybot -= delta;
	}

	delta = abs(area->r_ytop) % limit;
	if (delta > 0)
	{
	    if (area->r_ytop < 0)
		area->r_ytop += delta;
	    else
	    {
		area->r_ytop -= delta;
		area->r_ytop += limit;
	    }
	}
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBridgeFunc2 --
 *
 * 	Called for each relevant tile during bridge operations.  The
 *	bridge operation is responsible for preventing a grow-shrink
 *	pair of operations from leaving width or spacing DRC errors,
 *	which happens when tiles are overlapping at a corner with the
 *	overlap failing to meet the minimum width requirement.  The
 *	bridge operation adds a bridge of material over the pinch
 *	point that solves the minimum width requirement, adding a
 *	minimum amount of material to do so.
 *
 *	The current version of this routine adds material on a stair-step
 *	pattern;  preferably this should be extended to create material
 *	at allowed angles, where the allowed angles (90, 45, or any) are
 *	specified as an option to the bridge statement in the tech file.
 *
 *	growDistance is equal to the spacing rule distance needing to be
 *	satisfied.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Paints into cifNewPlane.  Tiles in old plane are tagged with
 *	a static value in ClientData, which does not need to be reset
 *	since the old plane will be free'd.
 * ----------------------------------------------------------------------------
 */

int
cifBridgeFunc2(tile, brs)
    Tile *tile;
    BridgeStruct *brs;
{
    Plane *plane = brs->plane;
    Rect area;
    Tile *tp1, *tp2, *tpx;
    int width = brs->bridge->br_width;
    int wtest;
    int spacing = growDistance;
    BridgeCheckStruct brcs;
    int cifBridgeCheckFunc();	/* Forward reference */

    /* If tile is marked, then it has been handled, so ignore it */
    if (tile->ti_client != (ClientData)CIF_UNPROCESSED) return 0;

    /* Find each tile outside corner (only two cases need to be checked) */

    /* Check for NE outside corner */
    tp1 = TR(tile);  /* Tile on right side at the top of this tile */
    tp2 = RT(tile);  /* Tile on top side at the right of this tile */
    if ((TiGetLeftType(tp1) == CIF_SOLIDTYPE) &&
	    (TiGetBottomType(tp2) == CIF_SOLIDTYPE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile) - spacing;
	area.r_xtop = RIGHT(tile) + width;
	area.r_ybot = TOP(tile) - spacing;
	area.r_ytop = TOP(tile) + width;

	/* Find violator tiles */
	brcs.tile = tile;
	brcs.area = &area;
	brcs.direction = BRIDGE_SW;
	brcs.checktype = CIF_SOLIDTYPE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &DBSpaceBits, cifBridgeCheckFunc, (ClientData)&brcs) == 1)
	{
	    tpx = brcs.violator;

	    area.r_xbot = RIGHT(tile);
	    area.r_ybot = TOP(tile);
	    area.r_xtop = LEFT(tpx);
	    area.r_ytop = BOTTOM(tpx);

	    GetExpandedAreaGrid(width, TRUE, &area);

	    /* Trivial implementation: fill box */
	    /* (to do: use stairstep to avoid filling unnecessary areas) */
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	}
    }

    /* Check for SE outside corner */
    for (tp1 = TR(tile); BOTTOM(tp1) > BOTTOM(tile); tp1 = LB(tp1));
    for (tp2 = LB(tile); RIGHT(tp2) < RIGHT(tile); tp2 = TR(tp2));
    if ((TiGetLeftType(tp1) == CIF_SOLIDTYPE) &&
	    (TiGetTopType(tp2) == CIF_SOLIDTYPE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile) - spacing;
	area.r_xtop = RIGHT(tile) + width;
	area.r_ybot = BOTTOM(tile) - width;
	area.r_ytop = BOTTOM(tile) + spacing;

	/* Find violator tiles */
	brcs.tile = tile;
	brcs.area = &area;
	brcs.direction = BRIDGE_NW;
	brcs.checktype = CIF_SOLIDTYPE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &DBSpaceBits, cifBridgeCheckFunc, (ClientData)&brcs) == 1)
	{
	    tpx = brcs.violator;

	    area.r_xbot = RIGHT(tile);
	    area.r_ybot = TOP(tpx);
	    area.r_xtop = LEFT(tpx);
	    area.r_ytop = BOTTOM(tile);

	    GetExpandedAreaGrid(width, TRUE, &area);

	    /* Trivial implementation: fill box */
	    /* (to do: use stairstep to avoid filling unnecessary areas) */
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	}
    }
    return 0;
}

/*
 *-----------------------------------------------------------------------
 * Callback function for cifBridgeFunc1 and cifBridgeFunc2 to find if
 * there are violator cells in the search area.	 If a violator cell is
 * found, then put the tile pointer in the BridgeCheckStruct and return
 * value 1 to stop the search.	Otherwise return 0 to keep going.
 *-----------------------------------------------------------------------
 */

int
cifBridgeCheckFunc(tile, brcs)
    Tile *tile;
    BridgeCheckStruct *brcs;
{
    int dir = brcs->direction;
    Tile *self = brcs->tile;
    Tile *tp1, *tp2;
    TileType checktype = brcs->checktype;

    if (self == tile) return 0;	    /* Ignore the triggering tile */

    switch (dir) {
	case BRIDGE_NW:
	    /* Ignore tile if NW corner is not in the search area */
	    for (tp1 = RT(tile); LEFT(tp1) > LEFT(tile); tp1 = BL(tp1));
	    if (LEFT(tile) <= brcs->area->r_xbot || TOP(tile) >= brcs->area->r_ytop)
		break;
	    /* Check that this is not a false corner */
	    else if (TiGetBottomType(tp1) == TiGetTopType(tile))
		break;
	    /* Ignore tile if split, and SE corner is clipped */
	    if (TiGetRightType(tile) == checktype || TiGetBottomType(tile) == checktype)
		break;
	    for (tp2 = BL(tile); TOP(tp2) < TOP(tile); tp2 = RT(tp2));
	    if ((TiGetBottomType(tp1) == checktype) &&
		    (TiGetRightType(tp2) == checktype))
	    {
		brcs->violator = tile;
		return 1;	/* Violator found */
	    }
	    break;
	case BRIDGE_SW:
	    /* Ignore tile if SW corner is not in the search area */
	    tp1 = LB(tile);
	    if (LEFT(tile) <= brcs->area->r_xbot || BOTTOM(tile) <= brcs->area->r_ybot)
		break;
	    /* Check that this is not a false corner */
	    else if (TiGetTopType(tp1) == TiGetBottomType(tile))
		break;
	    /* Ignore tile if split, and NE corner is clipped */
	    if (TiGetRightType(tile) == checktype || TiGetTopType(tile) == checktype)
		break;
	    tp2 = BL(tile);
	    if ((TiGetTopType(tp1) == checktype) ||
		    (TiGetRightType(tp2) == checktype))
	    {
		brcs->violator = tile;
		return 1;	/* Violator found */
	    }
	    break;
    }
    return 0;	/* Nothing found here, so keep going */
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifCloseFunc --
 *
 * 	Called for each relevant tile during close operations.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Paints into cifNewPlane.  Tiles in old plane are tagged with
 *	a static value in ClientData, which does not need to be reset
 *	since the old plane will be free'd.
 * ----------------------------------------------------------------------------
 */

#define CLOSE_SEARCH 0
#define CLOSE_FILL   1
#define CLOSE_DONE   2

int
cifCloseFunc(tile, plane)
    Tile *tile;
    Plane *plane;
{
    Rect area, newarea;
    int atotal;
    int cifGatherFunc();

    /* If tile is marked, then it has been handled, so ignore it */
    if (tile->ti_client != (ClientData)CIF_UNPROCESSED) return 0;

    atotal = 0;

    /* Search all sides for connected space tiles, and accumulate the total */
    /* area.  If any connected tile borders infinity, then stop searching   */
    /* because the area is not enclosed.				    */

    cifGatherFunc(tile, &atotal, CLOSE_SEARCH);

    /* If the total area is smaller than the rule area, then paint all the  */
    /* tile areas into the destination plane.				    */

    if ((atotal != INFINITY) && (atotal < growDistance))
    {
	cifGatherFunc(tile, &atotal, CLOSE_FILL);
    }
    else
    {
	cifGatherFunc(tile, &atotal, CLOSE_DONE);
    }

    return 0;
}

int
cifGatherFunc(tile, atotal, mode)
    Tile *tile;
    int *atotal;
    bool mode;
{
    Tile *tp;
    TileType type;
    dlong locarea;
    Rect area, newarea;
    ClientData cdata = (mode == CLOSE_SEARCH) ? (ClientData)CIF_UNPROCESSED :
	    (ClientData)CIF_PENDING;

    static Stack *GatherStack = (Stack *)NULL;

    if (GatherStack == (Stack *)NULL)
	GatherStack = StackNew(64);

    STACKPUSH(tile, GatherStack);
    while (!StackEmpty(GatherStack))
    {
	tile = (Tile *)STACKPOP(GatherStack);

	/* Ignore if tile has already been processed */
	if (tile->ti_client != cdata) continue;

	TiToRect(tile, &area);

	/* Boundary tiles indicate an unclosed area, so set the area total to 	*/
	/* INFINITY and don't try to run calculations on it.  NOTE:		*/
	/* TiPlaneRect is slightly smaller than the plane boundaries on all	*/
	/* sides.								*/

    	if ((area.r_xbot <= TiPlaneRect.r_xbot) ||
		(area.r_ybot <= TiPlaneRect.r_ybot) ||
	    	(area.r_xtop >= TiPlaneRect.r_xtop) ||
		(area.r_ytop >= TiPlaneRect.r_ytop))
	    *atotal = INFINITY;

    	/* Stop accumulating if already larger than growDistance to avoid the   */
    	/* possibility of integer overflow.					*/
    	if (mode == CLOSE_SEARCH)
    	{
	    if ((*atotal != INFINITY) && (*atotal < growDistance))
	    {
	    	locarea = (dlong)(area.r_xtop - area.r_xbot)
				* (dlong)(area.r_ytop - area.r_ybot);
	        if (IsSplit(tile)) locarea /= 2;
	        if (locarea > (dlong)INFINITY)
		    *atotal = INFINITY;
	        else
		    *atotal += (int)locarea;
	    }
        }
        else if (mode == CLOSE_FILL)
        {
	    TileType dinfo = TiGetTypeExact(tile);

	    /* The tile type cannot be depended on to have the TT_SIDE bit set	*/
	    /* for the side of the tile that is TT_SPACE.  So set the side bit	*/
	    /* manually.							*/

	    if (IsSplit(tile))
	    {
	        if (TiGetLeftType(tile) == TT_SPACE)
		    dinfo &= ~TT_SIDE;
	        else
		    dinfo |= TT_SIDE;
	    }

	    DBNMPaintPlane(cifPlane, dinfo, &area, CIFPaintTable, (PaintUndoInfo *)NULL);
	    CIFTileOps++;
        }

        if (mode == CLOSE_SEARCH)
	    tile->ti_client = (ClientData)CIF_PENDING;
        else
	    tile->ti_client = (ClientData)CIF_PROCESSED;

        /* Look for additional neighboring space tiles */
        /* Check top */
        if (area.r_ytop != TiPlaneRect.r_ytop)
            for (tp = RT(tile); RIGHT(tp) > LEFT(tile); tp = BL(tp))
	        if (tp->ti_client == cdata && TiGetBottomType(tp) == TT_SPACE)
		{
		    STACKPUSH(tp, GatherStack);
		}

    	/* Check bottom */
    	if (area.r_ybot != TiPlaneRect.r_ybot)
            for (tp = LB(tile); LEFT(tp) < RIGHT(tile); tp = TR(tp))
	    	if (tp->ti_client == cdata && TiGetTopType(tp) == TT_SPACE)
		{
		    STACKPUSH(tp, GatherStack);
		}

    	/* Check left */
    	if (area.r_xbot != TiPlaneRect.r_xbot)
	    for (tp = BL(tile); BOTTOM(tp) < TOP(tile); tp = RT(tp))
	    	if (tp->ti_client == cdata && TiGetRightType(tp) == TT_SPACE)
		{
		    STACKPUSH(tp, GatherStack);
		}

    	/* Check right */
    	if (area.r_xtop != TiPlaneRect.r_xtop)
	    for (tp = TR(tile); TOP(tp) > BOTTOM(tile); tp = LB(tp))
	    	if (tp->ti_client == cdata && TiGetLeftType(tp) == TT_SPACE)
		{
		    STACKPUSH(tp, GatherStack);
		}
    }
    return 0;
}

/*--------------------------------------------------------------*/
/* Support routines and definitions for cifSquaresFillArea	*/
/*--------------------------------------------------------------*/

/*------------------------------------------------------*/
/* Data structure used for identifying contact strips	*/
/*------------------------------------------------------*/

typedef struct _linkedStrip {
    Rect	area;
    bool	vertical;	/* Tile is vertical */
    bool	shrink_ld;	/* Shrink left or down before creating cuts */
    bool	shrink_ur;	/* Shrink right or up before creating cuts */
    struct _linkedStrip *strip_next;
} linkedStrip;

typedef struct
{
   int size;
   int pitch;
   linkedStrip *strips;
} StripsData;

/*
 *-------------------------------------------------------
 *
 * cifSquaresInitFunc --
 *
 *	Find the first unprocessed tile in the plane.
 *
 * Results:
 *	Return 1 to stop the search and process.
 *	Otherwise, return 0 to keep the search going.
 *
 *-------------------------------------------------------
 */

int
cifSquaresInitFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;
{
    if (tile->ti_client == (ClientData) CIF_UNPROCESSED)
	return 1;
    else
	return 0;
}

/*
 *-------------------------------------------------------
 *
 * cifSquaresStripFunc --
 *
 *	Find vertical or horizontal strips of contact
 * material that is between 1 and 2 contact cuts wide.
 * Generate and return a list of all such strips.
 *
 * Results:  Return 0 to keep the search going.
 *
 *-------------------------------------------------------
 */

int
cifSquaresStripFunc(tile, stripsData)
    Tile *tile;
    StripsData *stripsData;
{
    bool vertical;
    int width, height;
    linkedStrip *newStrip;
    Tile *tp, *tp2;
    Rect bbox;

    if (IsSplit(tile))
	return 0;
    TiToRect(tile, &bbox);

    /* Check if the tile is wide enough for exactly one cut */

    width = bbox.r_xtop - bbox.r_xbot;
    height = bbox.r_ytop - bbox.r_ybot;

    if (height > width)
    {
	vertical = TRUE;
	height = width;
    }
    else
	vertical = FALSE;

    if ((height < stripsData->size) || (height >=
		(stripsData->size + stripsData->pitch)))
	return 0;

    /* Ignore strips that are part of a larger	*/
    /* collection of non-manhattan geometry.	*/

    for (tp = BL(tile); BOTTOM(tp) < TOP(tile); tp = RT(tp))
	if (IsSplit(tp))
	    break;
    if (BOTTOM(tp) < TOP(tile))
	return 0;

    /* Note that the max horizontal stripes rule guarantees	*/
    /* that a tile is always bounded on left and right by	*/
    /* TT_SPACE.  Thus, we only need to search the top and	*/
    /* bottom boundaries of horizontal tiles.			*/

    if (vertical)
    {
	newStrip = (linkedStrip *)mallocMagic(sizeof(linkedStrip));
	newStrip->area = bbox;
	newStrip->vertical = TRUE;
	newStrip->shrink_ur = (TTMaskHasType(&CIFSolidBits,
		TiGetBottomType(RT(tile)))) ? TRUE : FALSE;
	newStrip->shrink_ld = (TTMaskHasType(&CIFSolidBits,
		TiGetTopType(LB(tile)))) ? TRUE : FALSE;
	newStrip->strip_next = stripsData->strips;
	stripsData->strips = newStrip;
    }
    else
    {
	int segstart, segend;
	int matchstart, matchend;

	tp = RT(tile);
	segend = RIGHT(tile);
	while (RIGHT(tp) > LEFT(tile))
	{
	    /* Isolate segments of space along the top of the tile */

	    while ((RIGHT(tp) > LEFT(tile)) &&
			TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
		tp = BL(tp);
	    segend = MIN(segend, RIGHT(tp));
	    while ((RIGHT(tp) > LEFT(tile)) &&
			TTMaskHasType(&DBSpaceBits, TiGetBottomType(tp)))
		tp = BL(tp);
	    segstart = MAX(LEFT(tile), RIGHT(tp));
	    if (segend <= segstart) break;

	    /* Find matching segments along the bottom of the  tile */

	    for (tp2 = LB(tile); RIGHT(tp2) < segstart; tp2 = TR(tp2));

	    while (LEFT(tp2) < segend)
	    {
		while (RIGHT(tp2) < segstart) tp2 = TR(tp2);
		while ((LEFT(tp2) < segend) &&
				TTMaskHasType(&CIFSolidBits, TiGetTopType(tp2)))
		    tp2 = TR(tp2);
		matchstart = MAX(LEFT(tp2), segstart);
		while ((LEFT(tp2) < segend) &&
				TTMaskHasType(&DBSpaceBits, TiGetTopType(tp2)))
		    tp2 = TR(tp2);
		matchend = MIN(LEFT(tp2), segend);
		if (matchend <= matchstart) break;

		/* Process the strip */

		newStrip = (linkedStrip *)mallocMagic(sizeof(linkedStrip));
		newStrip->area = bbox;
		newStrip->area.r_xbot = matchstart;
		newStrip->area.r_xtop = matchend;
		newStrip->vertical = FALSE;
		newStrip->strip_next = stripsData->strips;
		newStrip->shrink_ur = (matchend != RIGHT(tile)) ? TRUE : FALSE;
		newStrip->shrink_ld = (matchstart != LEFT(tile)) ? TRUE : FALSE;

		stripsData->strips = newStrip;
	    }
	}
    }
    return 0;
}

/*
 *-------------------------------------------------------
 *
 * cifUnconnectFunc --
 *
 *	Find space tiles inside a possible contact area
 *
 * Results:	Return 1 to stop the ongoing search.
 *
 *-------------------------------------------------------
 */


int
cifUnconnectFunc(tile, clientData)
    Tile *tile;
    ClientData clientData;	/* unused */
{
    TileType t = TiGetTypeExact(tile);
    if (t == TT_SPACE) return 1;
    else if (t & TT_DIAGONAL) return 1;
    else if (tile->ti_client != (ClientData)CIF_PROCESSED) return 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifRectBoundingBox --
 *
 * 	Fill regions of the current CIF plane with rectangles that represent
 *	the bounding box of each unconnected area.  This function "cleans
 *	up" areas processed by multiple rules and removes notches and
 *	cut-outs.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *
 * ----------------------------------------------------------------------------
 */

void
cifRectBoundingBox(op, cellDef, plane)
    CIFOp *op;
    CellDef *cellDef;
    Plane *plane;
{
    Tile *tile = NULL, *t, *tp;
    Rect bbox, area, *maxr;
    int i, j, savecount;
    TileType type;
    bool simple;
    static Stack *BoxStack = (Stack *)NULL;

    if (BoxStack == (Stack *)NULL)
	BoxStack = StackNew(64);

    while (DBSrPaintArea((Tile *)tile, plane, &TiPlaneRect, &CIFSolidBits,
		cifSquaresInitFunc, (ClientData)NULL) != 0)
    {
	/* Now, search for (nontrivially) connected tiles in all	*/
	/* directions.  Mark the tiles, and record the bounding box.	*/
	/* (Largely copied from cifSquaresFillArea)			*/

	simple = TRUE;
	tile = plane->pl_hint;
	TiToRect(tile, &bbox);

	PUSHTILE(tile, BoxStack);
	while (!StackEmpty(BoxStack))
	{
	    t = (Tile *) STACKPOP(BoxStack);
	    if (t->ti_client != (ClientData)CIF_PENDING) continue;
            t->ti_client = (ClientData)CIF_PROCESSED;

	    /* Adjust bounding box */
	    TiToRect(t, &area);
	    GeoInclude(&area, &bbox);

	    if (IsSplit(t)) simple = FALSE;

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, BoxStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetRightType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, BoxStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetTopType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, BoxStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetLeftType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, BoxStack);
		}
	}

	if (op->co_client == (ClientData)1)	/* external */
	{
	    DBPaintPlane(cifPlane, &bbox, CIFPaintTable, (PaintUndoInfo *)NULL);
	    CIFTileOps++;
	}
	else	/* internal */
	{
	    if (simple)
	    {
		DBPaintPlane(cifPlane, &bbox, CIFPaintTable, (PaintUndoInfo *)NULL);
		CIFTileOps++;
	    }
	    else
	    {
		maxr = FindMaxRectangle2(&bbox, tile, plane, NULL);
		DBPaintPlane(cifPlane, maxr, CIFPaintTable, (PaintUndoInfo *)NULL);
		CIFTileOps++;
	    }
	}

	/* Clear the tiles that were processed in this set */

	tile->ti_client = (ClientData)CIF_IGNORE;
	STACKPUSH(tile, BoxStack);
	while (!StackEmpty(BoxStack))
	{
	    t = (Tile *) STACKPOP(BoxStack);

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, BoxStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, BoxStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, BoxStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, BoxStack);
		}
	}
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquaresFillArea --
 *
 *	Fill areas in the current CIF output plane with contact cuts based on
 *	the SQUARES operation passed in "op".  This differs from the original
 *	tile-based contact cut generation by collecting all connected tiles
 *	in an area, and placing cuts relative to that area's bounding box.
 *	A tile search is used to select the parts of any non-rectangular area
 *	inside the bounding box that allow contact cuts, which lets cuts
 *	be placed across tile boundaries and inside non-manhattan tiles.
 *	It also allows contacts to be placed inside complex structures such
 *	as (possibly intersecting) guardrings.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *
 * ----------------------------------------------------------------------------
 */

void
cifSquaresFillArea(op, cellDef, plane)
    CIFOp *op;
    CellDef *cellDef;
    Plane *plane;
{
    Tile *tile, *t, *tp;
    Rect bbox, area, square, cut, llcut;
    int nAcross, nUp, left, pitch, size, diff, right;
    int i, j, k, savecount;
    TileType type;
    SquaresData *squares = (SquaresData *)op->co_client;
    StripsData stripsData;
    linkedStrip *stripList;
    bool simple;
    static Stack *CutStack = (Stack *)NULL;

    pitch = squares->sq_size + squares->sq_sep;
    size = squares->sq_size + 2 * squares->sq_border;
    diff = squares->sq_sep - 2 * squares->sq_border;

    if (CutStack == (Stack *)NULL)
	CutStack = StackNew(64);

    /* Two-pass algorithm */

    /* Search the plane for "strips", sections of contact that are only	*/
    /* wide enough for 1 cut.  Process them separately, then erase the	*/
    /* processed areas.	  The purpose of this is to avoid applying the	*/
    /* contact matrix algorithm on non-convex spaces, such as guard	*/
    /* rings, where centering the matrix on the bounding box of the	*/
    /* contact area may produce a matrix misaligned with the contact	*/
    /* strips, preventing any contacts from being drawn!  Due to the	*/
    /* maximum horizontal stripes rule for corner stitched tiles, we	*/
    /* need only identify vertical contact strips.  After processing	*/
    /* and erasing them, all remaining areas will be convex.  This	*/
    /* algorithm allows contacts to be drawn in any arbitrary geometry.	*/

    stripsData.size = size;
    stripsData.pitch = pitch;
    stripsData.strips = NULL;
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifSquaresStripFunc, (ClientData)&stripsData);

    /* Generate cuts in each strip found, then erase the strip */

    stripList = stripsData.strips;
    while (stripList != NULL)
    {
	Rect stripLess = stripList->area;

	if (diff > 0)
	{
	    if (stripList->vertical)
	    {
		if (stripList->shrink_ur) stripLess.r_ytop -= diff;
		if (stripList->shrink_ld) stripLess.r_ybot += diff;
	    }
	    else
	    {
		if (stripList->shrink_ur) stripLess.r_xtop -= diff;
		if (stripList->shrink_ld) stripLess.r_xbot += diff;
	    }
	}

	/* Create the cuts */

	if (op->co_opcode == CIFOP_SQUARES)
	    cifSquareFunc(&stripLess, op, &nUp, &nAcross, &llcut);
	else if (op->co_opcode == CIFOP_SQUARES_G)
	    cifSquareGridFunc(&stripLess, op, &nUp, &nAcross, &llcut);

	cut.r_ybot = llcut.r_ybot;
	cut.r_ytop = llcut.r_ytop;

	for (i = 0; i < nUp; i++)
	{
	    cut.r_xbot = llcut.r_xbot;
	    cut.r_xtop = llcut.r_xtop;
	    for (j = 0; j < nAcross; j++)
	    {
		DBPaintPlane(cifPlane, &cut, CIFPaintTable, (PaintUndoInfo *)NULL);
		cut.r_xbot += pitch;
		cut.r_xtop += pitch;
	    }
	    cut.r_ybot += pitch;
	    cut.r_ytop += pitch;
	}
	if (nUp == 0)
	{
	    if (stripList->shrink_ur == 0 && stripList->shrink_ld == 0)
	    {
		/* The following code is backwardly-compatible with the	 */
		/* original behavior of allowing cuts that do not have	 */
		/* sufficient border.  Here, we restrict that to contact */
		/* areas exactly matching the cut size.  There should be */
		/* a flag to allow contacts to be generated this way.	 */

		if ((stripList->area.r_xtop - stripList->area.r_xbot
			== squares->sq_size) && (stripList->area.r_ytop
			- stripList->area.r_ybot == squares->sq_size))
		{
		    DBPaintPlane(cifPlane, &stripList->area, CIFPaintTable,
				(PaintUndoInfo *)NULL);
		    CIFTileOps++;
		}
		else
		    CIFError(&stripList->area, "no room for contact cuts in area!");
	    }

	    /* Ad hoc rule catches problems due to contact areas of the proper	*/
	    /* size not fitting cuts because the grid offset prohibits it.	*/
	    else if (((stripList->area.r_ur.p_x - stripList->area.r_ll.p_x) *
			(stripList->area.r_ur.p_y - stripList->area.r_ll.p_y)) >
			2 * (pitch * pitch))
		CIFError(&stripList->area, "contact strip with no room for cuts!");
	}

	DBPaintPlane(plane, &stripList->area, CIFEraseTable,
		(PaintUndoInfo *) NULL);
	freeMagic(stripList);
	stripList = stripList->strip_next;
    }

    /* 2nd pass:  Search the plane for unmarked tiles */

    while (DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifSquaresInitFunc, (ClientData)NULL) != 0)
    {
	/* Now, search for (nontrivially) connected tiles in all	*/
	/* directions.  Mark the tiles, and record the bounding box.	*/
	/* (Largely copied from cifBloatAllFunc)			*/

	simple = TRUE;
	tile = plane->pl_hint;
	TiToRect(tile, &bbox);

	PUSHTILE(tile, CutStack);
	while (!StackEmpty(CutStack))
	{
	    t = (Tile *) STACKPOP(CutStack);
	    if (t->ti_client != (ClientData)CIF_PENDING) continue;
            t->ti_client = (ClientData)CIF_PROCESSED;

	    /* Adjust bounding box */
	    TiToRect(t, &area);
	    GeoInclude(&area, &bbox);

	    if (IsSplit(t)) simple = FALSE;

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetRightType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetTopType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetLeftType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}
	}

	savecount = CIFTileOps;

	for (k = 0; k < 3; k++)	/* prepare for up to 3 passes */
	{
	    /* Determine the contact cut offsets from the bounding box */

	    if (op->co_opcode == CIFOP_SQUARES)
		cifSquareFunc(&bbox, op, &nUp, &nAcross, &llcut);
	    else if (op->co_opcode == CIFOP_SQUARES_G)
		cifSquareGridFunc(&bbox, op, &nUp, &nAcross, &llcut);

	    cut.r_ybot = llcut.r_ybot;
	    cut.r_ytop = llcut.r_ytop;

	    /* For each contact cut area, check that there is	*/
	    /* no whitespace					*/

	    for (i = 0; i < nUp; i++)
	    {
		cut.r_xbot = llcut.r_xbot;
		cut.r_xtop = llcut.r_xtop;

		square.r_ybot = cut.r_ybot - squares->sq_border;
		square.r_ytop = cut.r_ytop + squares->sq_border;

		for (j = 0; j < nAcross; j++)
		{
		    square.r_xbot = cut.r_xbot - squares->sq_border;
		    square.r_xtop = cut.r_xtop + squares->sq_border;

    		    /* If there is only one simple rectangle in the	*/
		    /* area, the area is convex, so we don't have to	*/
		    /* check for unconnected regions.			*/

		    if (simple || DBSrPaintArea((Tile *)tile, plane, &square,
				&DBAllTypeBits, cifUnconnectFunc,
				(ClientData)NULL) == 0)
		    {
			DBPaintPlane(cifPlane, &cut, CIFPaintTable,
				(PaintUndoInfo *)NULL);
			CIFTileOps++;
		    }
		    cut.r_xbot += pitch;
		    cut.r_xtop += pitch;
		}
		cut.r_ybot += pitch;
		cut.r_ytop += pitch;
	    }
	    if (savecount != CIFTileOps) break;

	    /* In non-Manhattan regions with beveled corners, where	*/
	    /* the bounding box has space for 2 contacts, there may not	*/
	    /* be space in the shape itself for more than one.  We will	*/
	    /* attempt to shrink X, Y, and/or both to fit (up to 3	*/
	    /* passes may be necessary).				*/

	    if (nUp == 2)
	    {
		int bdiff = 1 + (bbox.r_ytop - bbox.r_ybot) -
			(2 * (squares->sq_size + squares->sq_border) +
			squares->sq_sep);
		if (bdiff & 0x1) bdiff++;	/* bdiff must be even	*/
		bdiff >>= 1;			/* take half		*/
		bbox.r_ytop -= bdiff;
		bbox.r_ybot += bdiff;
	    }
	    else if (nAcross == 2)
	    {
		int bdiff = 1 + (bbox.r_xtop - bbox.r_xbot) -
			(2 * (squares->sq_size + squares->sq_border) +
			squares->sq_sep);
		if (bdiff & 0x1) bdiff++;	/* bdiff must be even	*/
		bdiff >>= 1;			/* take half		*/
		bbox.r_xtop -= bdiff;
		bbox.r_xbot += bdiff;
	    }
	    else
		break;
	}
	if (savecount == CIFTileOps)
	    CIFError(&bbox, "no room for contacts in area!");

	/* Clear the tiles that were processed */

	tile->ti_client = (ClientData)CIF_IGNORE;
	STACKPUSH(tile, CutStack);
	while (!StackEmpty(CutStack))
	{
	    t = (Tile *) STACKPOP(CutStack);

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}
	}
    }

    /* Clear all the tiles that were processed */
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifProcessResetFunc, (ClientData)NULL);
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSlotsFillArea --
 *
 *	Fill areas in the current CIF output plane with contact cuts based on
 *	the SLOTS operation passed in "op".  This routine is like
 *	cifSquaresFillArea but handles X and Y dimensions independently.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *
 * ----------------------------------------------------------------------------
 */

void
cifSlotsFillArea(op, cellDef, plane)
    CIFOp *op;
    CellDef *cellDef;
    Plane *plane;
{
    Tile *tile, *t, *tp;
    Rect bbox, area, square, cut, llcut;
    int nAcross, nUp, left, spitch, lpitch, ssize, lsize, offset;
    int diff, right;
    int xpitch, ypitch, xborder, yborder, xdiff, ydiff;
    int i, j, k, savecount;
    TileType type;
    SlotsData *slots = (SlotsData *)op->co_client;
    StripsData stripsData;
    linkedStrip *stripList;
    bool simple, vertical;
    static Stack *CutStack = (Stack *)NULL;

    spitch = slots->sl_ssize + slots->sl_ssep;
    lpitch = slots->sl_lsize + slots->sl_lsep;
    ssize = slots->sl_ssize + 2 * slots->sl_sborder;
    lsize = slots->sl_lsize + 2 * slots->sl_lborder;

    /* This may not be good in all cases!  Amount to shorten a strip	*/
    /* depends on the orientation of the cuts on either side of the	*/
    /* connected strip edge. . .					*/
    diff = slots->sl_lsep - slots->sl_lborder - slots->sl_sborder;

    if (CutStack == (Stack *)NULL)
	CutStack = StackNew(64);

    /* Two-pass algorithm */

    /* Search the plane for "strips", sections of contact that are only	*/
    /* wide enough for 1 cut.  Process them separately, then erase the	*/
    /* processed areas.	  The purpose of this is to avoid applying the	*/
    /* contact matrix algorithm on non-convex spaces, such as guard	*/
    /* rings, where centering the matrix on the bounding box of the	*/
    /* contact area may produce a matrix misaligned with the contact	*/
    /* strips, preventing any contacts from being drawn!  Due to the	*/
    /* maximum horizontal stripes rule for corner stitched tiles, we	*/
    /* need only identify vertical contact strips.  After processing	*/
    /* and erasing them, all remaining areas will be convex.  This	*/
    /* algorithm allows contacts to be drawn in any arbitrary geometry.	*/

    stripsData.size = ssize;
    stripsData.pitch = spitch;
    stripsData.strips = NULL;
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifSquaresStripFunc, (ClientData)&stripsData);

    /* Generate cuts in each strip found, then erase the strip */

    stripList = stripsData.strips;
    while (stripList != NULL)
    {
	Rect stripLess = stripList->area;

	if (diff > 0)
	{
	    if (stripList->vertical)
	    {
		if (stripList->shrink_ur) stripLess.r_ytop -= diff;
		if (stripList->shrink_ld) stripLess.r_ybot += diff;
	    }
	    else
	    {
		if (stripList->shrink_ur) stripLess.r_xtop -= diff;
		if (stripList->shrink_ld) stripLess.r_xbot += diff;
	    }
	}

	/* Create the cuts */

	cifSlotFunc(&stripLess, op, &nUp, &nAcross, &llcut, stripList->vertical);

	cut = llcut;

	if (stripList->vertical)
	{
	    for (i = 0; i < nUp; i++)
	    {
		DBPaintPlane(cifPlane, &cut, CIFPaintTable, (PaintUndoInfo *)NULL);
		cut.r_ybot += lpitch;
		cut.r_ytop += lpitch;
	    }
	}
	else
	{
	    for (i = 0; i < nAcross; i++)
	    {
		DBPaintPlane(cifPlane, &cut, CIFPaintTable, (PaintUndoInfo *)NULL);
		cut.r_xbot += lpitch;
		cut.r_xtop += lpitch;
	    }
	}

	if (nUp == 0 || nAcross == 0)
	{
	    if (stripList->shrink_ur == 0 && stripList->shrink_ld == 0)
	    {
		/* The following code is backwardly-compatible with the	 */
		/* original behavior of allowing cuts that do not have	 */
		/* sufficient border.  Here, we restrict that to contact */
		/* areas exactly matching the cut size.  There should be */
		/* a flag to allow contacts to be generated this way.	 */

		if (((stripList->area.r_xtop - stripList->area.r_xbot
			== slots->sl_ssize) && (stripList->area.r_ytop
			- stripList->area.r_ybot == slots->sl_lsize)) ||
			((stripList->area.r_xtop - stripList->area.r_xbot
			== slots->sl_lsize) && (stripList->area.r_ytop
			- stripList->area.r_ybot == slots->sl_ssize)))
		{
		    DBPaintPlane(cifPlane, &stripList->area, CIFPaintTable,
				(PaintUndoInfo *)NULL);
		    CIFTileOps++;
		}
		else
		    CIFError(&stripList->area, "no room for contact cuts in area!");
	    }

	    /* Ad hoc rule catches problems due to contact areas of the proper	*/
	    /* size not fitting cuts because the grid offset prohibits it.	*/
	    else if (((stripList->area.r_ur.p_x - stripList->area.r_ll.p_x) *
			(stripList->area.r_ur.p_y - stripList->area.r_ll.p_y)) >
			2 * (lpitch * spitch))
		CIFError(&stripList->area, "contact strip with no room for cuts!");
	}

	DBPaintPlane(plane, &stripList->area, CIFEraseTable,
		(PaintUndoInfo *) NULL);
	freeMagic(stripList);
	stripList = stripList->strip_next;
    }

    /* 2nd pass:  Search the plane for unmarked tiles */

    while (DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifSquaresInitFunc, (ClientData)NULL) != 0)
    {
	/* Now, search for (nontrivially) connected tiles in all	*/
	/* directions.  Mark the tiles, and record the bounding box.	*/
	/* (Largely copied from cifBloatAllFunc)			*/

	simple = TRUE;
	tile = plane->pl_hint;
	TiToRect(tile, &bbox);

	PUSHTILE(tile, CutStack);
	while (!StackEmpty(CutStack))
	{
	    t = (Tile *) STACKPOP(CutStack);
	    if (t->ti_client != (ClientData)CIF_PENDING) continue;
            t->ti_client = (ClientData)CIF_PROCESSED;

	    /* Adjust bounding box */
	    TiToRect(t, &area);
	    GeoInclude(&area, &bbox);

	    if (IsSplit(t)) simple = FALSE;

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetBottomType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetRightType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetTopType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (TTMaskHasType(&CIFSolidBits, TiGetLeftType(tp)))
		{
		    simple = FALSE;
		    PUSHTILE(tp, CutStack);
		}
	}

	/* May want to attempt a second pass with the orthogonal alignment? */
	if ((bbox.r_xtop - bbox.r_xbot) > (bbox.r_ytop - bbox.r_ybot))
	    vertical = FALSE;
	else
	    vertical = TRUE;

	if (vertical)
	{
	    xpitch = spitch;
	    ypitch = lpitch;
	    xborder = slots->sl_sborder;
	    yborder = slots->sl_lborder;
	    xdiff = 2 * (slots->sl_ssize + slots->sl_sborder) + slots->sl_ssep;
	    ydiff = 2 * (slots->sl_lsize + slots->sl_lborder) + slots->sl_lsep;
	}
	else
	{
	    xpitch = lpitch;
	    ypitch = spitch;
	    xborder = slots->sl_lborder;
	    yborder = slots->sl_sborder;
	    xdiff = 2 * (slots->sl_lsize + slots->sl_lborder) + slots->sl_lsep;
	    ydiff = 2 * (slots->sl_ssize + slots->sl_sborder) + slots->sl_ssep;
	}

	savecount = CIFTileOps;

	for (k = 0; k < 3; k++)	/* prepare for up to 3 passes */
	{
	    /* Determine the contact cut offsets from the bounding box */

	    cifSlotFunc(&bbox, op, &nUp, &nAcross, &llcut, vertical);

	    cut.r_ybot = llcut.r_ybot + slots->sl_start;
	    cut.r_ytop = llcut.r_ytop + slots->sl_start;

	    /* For each contact cut area, check that there is	*/
	    /* no whitespace					*/

	    offset = slots->sl_start;
	    for (i = 0; i < nUp; i++)
	    {
		cut.r_xbot = llcut.r_xbot + offset;
		cut.r_xtop = llcut.r_xtop + offset;

		square.r_ybot = cut.r_ybot - yborder;
		square.r_ytop = cut.r_ytop + yborder;

		for (j = 0; j < nAcross; j++)
		{
		    square.r_xbot = cut.r_xbot - xborder;
		    square.r_xtop = cut.r_xtop + xborder;

    		    /* If there is only one simple rectangle in the	*/
		    /* area, the area is convex, so we don't have to	*/
		    /* check for unconnected regions.			*/

		    if (simple || DBSrPaintArea((Tile *)tile, plane, &square,
				&DBAllTypeBits, cifUnconnectFunc,
				(ClientData)NULL) == 0)
		    {
			DBPaintPlane(cifPlane, &cut, CIFPaintTable,
				(PaintUndoInfo *)NULL);
			CIFTileOps++;
		    }
		    cut.r_xbot += xpitch;
		    cut.r_xtop += xpitch;
		}
		cut.r_ybot += ypitch;
		cut.r_ytop += ypitch;
		offset += slots->sl_offset;
		if (offset >= xpitch) offset -= xpitch;
	    }
	    if (savecount != CIFTileOps) break;

	    /* In non-Manhattan regions with beveled corners, where	*/
	    /* the bounding box has space for 2 contacts, there may not	*/
	    /* be space in the shape itself for more than one.  We will	*/
	    /* attempt to shrink X, Y, and/or both to fit (up to 3	*/
	    /* passes may be necessary).				*/

	    if (nUp == 2)
	    {
		int bdiff = 1 + (bbox.r_ytop - bbox.r_ybot) - ydiff;
		if (bdiff & 0x1) bdiff++;	/* bdiff must be even	*/
		bdiff >>= 1;			/* take half		*/
		bbox.r_ytop -= bdiff;
		bbox.r_ybot += bdiff;
	    }
	    else if (nAcross == 2)
	    {
		int bdiff = 1 + (bbox.r_xtop - bbox.r_xbot) - xdiff;
		if (bdiff & 0x1) bdiff++;	/* bdiff must be even	*/
		bdiff >>= 1;			/* take half		*/
		bbox.r_xtop -= bdiff;
		bbox.r_xbot += bdiff;
	    }
	    else
		break;
	}
	if (savecount == CIFTileOps)
	    CIFError(&bbox, "no room for contacts in area!");

	/* Clear the tiles that were processed */

	tile->ti_client = (ClientData)CIF_IGNORE;
	STACKPUSH(tile, CutStack);
	while (!StackEmpty(CutStack))
	{
	    t = (Tile *) STACKPOP(CutStack);

	    /* Top */
	    for (tp = RT(t); RIGHT(tp) > LEFT(t); tp = BL(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Left */
	    for (tp = BL(t); BOTTOM(tp) < TOP(t); tp = RT(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Bottom */
	    for (tp = LB(t); LEFT(tp) < RIGHT(t); tp = TR(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}

	    /* Right */
	    for (tp = TR(t); TOP(tp) > BOTTOM(t); tp = LB(tp))
		if (tp->ti_client == (ClientData)CIF_PROCESSED)
		{
		    tp->ti_client = (ClientData)CIF_IGNORE;
		    STACKPUSH(tp, CutStack);
		}
	}
    }

    /* Clear all the tiles that were processed */
    DBSrPaintArea((Tile *)NULL, plane, &TiPlaneRect, &CIFSolidBits,
		cifProcessResetFunc, (ClientData)NULL);
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBloatMaxFunc --
 *
 * 	Called once for each tile to be selectively bloated or
 *	shrunk using the CIFOP_BLOATMAX or CIFOP_BLOATMIN operation.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	Uses the bloat table in the current CIFOp to expand or shrink
 *	the tile, depending on which tiles it abuts.  The rectangular
 *	area of the tile is modified by moving each side in or out
 *	by the maximum bloat distance for any of its neighbors on
 *	that side.  The result is a new rectangle, which is OR'ed
 *	into the result plane.  Note:  any edge between two tiles of
 *	same type is given a zero bloat factor.
 *
 * ----------------------------------------------------------------------------
 */

int
cifBloatMaxFunc(tile, op)
    Tile *tile;			/* The tile to be processed. */
    CIFOp *op;			/* Describes the operation to be performed
				 * (all we care about is the opcode and
				 * bloat table).
				 */
{
    Rect area;
    int bloat, tmp;
    Tile *t;
    TileType type, otherType;
    BloatData *bloats = (BloatData *)op->co_client;

    /* Get the tile into CIF coordinates. */

    type = TiGetType(tile);
    TiToRect(tile, &area);
    area.r_xbot *= cifScale;
    area.r_ybot *= cifScale;
    area.r_xtop *= cifScale;
    area.r_ytop *= cifScale;

    /* See how much to adjust the left side of the tile. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = BL(tile); BOTTOM(t) < TOP(tile); t = RT(t))
    {
	otherType = TiGetType(t);
	if (otherType == type) continue;
	tmp = bloats->bl_distance[otherType];
	if (op->co_opcode == CIFOP_BLOATMAX)
	{
	    if (tmp > bloat) bloat = tmp;
	}
	else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
	area.r_xbot -= bloat;

    /* Now figure out how much to adjust the top side of the tile. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = RT(tile); RIGHT(t) > LEFT(tile); t = BL(t))
    {
	otherType = TiGetType(t);
	if (otherType == type) continue;
	tmp = bloats->bl_distance[otherType];
	if (op->co_opcode == CIFOP_BLOATMAX)
	{
	    if (tmp > bloat) bloat = tmp;
	}
	else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
	area.r_ytop += bloat;

    /* Now the right side. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = TR(tile); TOP(t) > BOTTOM(tile); t = LB(t))
    {
	otherType = TiGetType(t);
	if (otherType == type) continue;
	tmp = bloats->bl_distance[otherType];
	if (op->co_opcode == CIFOP_BLOATMAX)
	{
	    if (tmp > bloat) bloat = tmp;
	}
	else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
	area.r_xtop += bloat;

    /* Lastly, do the bottom side. */

    if (op->co_opcode == CIFOP_BLOATMAX) bloat = -10000000;
    else bloat = 10000000;
    for (t = LB(tile); LEFT(t) < RIGHT(tile); t = TR(t))
    {
	otherType = TiGetType(t);
	if (otherType == type) continue;
	tmp = bloats->bl_distance[otherType];
	if (op->co_opcode == CIFOP_BLOATMAX)
	{
	    if (tmp > bloat) bloat = tmp;
	}
	else if (tmp < bloat) bloat = tmp;
    }
    if ((bloat < 10000000) && (bloat > -10000000))
	area.r_ybot -= bloat;

    /* Make sure the tile didn't shrink into negativity.  If it's
     * ok, paint it into the new plane being built.
     */

    if ((area.r_xbot > area.r_xtop) || (area.r_ybot > area.r_ytop))
    {
	TiToRect(tile, &area);
	area.r_xbot *= cifScale;
	area.r_xtop *= cifScale;
	area.r_ybot *= cifScale;
	area.r_ytop *= cifScale;
	CIFError(&area, "tile inverted by shrink");
    }
    else
	DBNMPaintPlane(cifPlane, TiGetTypeExact(tile), &area,
		CIFPaintTable, (PaintUndoInfo *) NULL);

    CIFTileOps += 1;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * inside_triangle --
 *
 *	Test if the specified rectangle is completely inside the tile.
 *	Tile is presumed to be a split tile.
 *
 * Results:
 *	TRUE if inside, FALSE if outside or overlapping.
 *
 * Side Effects:
 *	None.
 *
 * Notes:
 *	This is an optimized version of the code in DBtiles.c.  It
 *	assumes that the square is never infinite.
 *
 * ----------------------------------------------------------------------------
 */

bool
inside_triangle(rect, tile)
    Rect *rect;
    Tile *tile;
{
    int theight, twidth;
    dlong f1, f2, f3, f4;

    theight = TOP(tile) - BOTTOM(tile);
    twidth = RIGHT(tile) - LEFT(tile);

    f1 = (dlong)(TOP(tile) - rect->r_ybot) * twidth;
    f2 = (dlong)(rect->r_ytop - BOTTOM(tile)) * twidth;

    if (SplitLeftType(tile) != TT_SPACE)
    {
        /* Inside-of-triangle check */
        f4 = (dlong)(rect->r_xbot - LEFT(tile)) * theight;
        if (SplitDirection(tile) ? (f1 > f4) : (f2 > f4))
	    return TRUE;
    }
    else
    {
        /* Inside-of-triangle check */
        f3 = (dlong)(RIGHT(tile) - rect->r_xtop) * theight;
        if (SplitDirection(tile) ? (f2 > f3) : (f1 > f3))
	    return TRUE;
    }
    return FALSE;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifContactFunc --
 *
 *	Called for each relevant tile when chopping up contacts into
 *	square cuts using the procedure of using a pre-defined cell
 *	definition of a single contact and arraying the cell.
 *	Technically, this is not a CIF function because CIF does not
 *	have an array method for cells, so there is no advantage to
 *	drawing lots of subcells in place of drawing lots of boxes.
 *	In GDS, however, the array method is much more compact than
 *	drawing individual cuts when the array size is larger than 1.
 *
 * Results:
 *	Normally returns 0 to keep the search going.  Return 1 if
 *	the contact type cannot be found, which halts the search.
 *
 * Side effects:
 *	Stuff is painted into cifPlane.
 *
 * ----------------------------------------------------------------------------
 */

int
cifContactFunc(tile, csi)
    Tile *tile;			/* Tile to be diced up. */
    CIFSquaresInfo *csi; 	/* Describes how to generate squares. */
{
    Rect area;
    int i, nAcross, j, nUp, left, bottom, pitch, halfsize;
    bool result;
    SquaresData *squares = csi->csi_squares;

    /* For now, don't allow squares on non-manhattan tiles */
    if (IsSplit(tile))
	return 0;

    TiToRect(tile, &area);
    pitch = squares->sq_size + squares->sq_sep;

    nAcross = (area.r_xtop - area.r_xbot + squares->sq_sep
	    - (2 * squares->sq_border)) / pitch;
    if (nAcross == 0)
    {
	left = (area.r_xbot + area.r_xtop - squares->sq_size) / 2;
	if (left >= area.r_xbot) nAcross = 1;
    }
    else
	left = (area.r_xbot + area.r_xtop + squares->sq_sep
		- (nAcross * pitch)) / 2;

    nUp = (area.r_ytop - area.r_ybot + squares->sq_sep
	    - (2 * squares->sq_border)) / pitch;
    if (nUp == 0)
    {
	bottom = (area.r_ybot + area.r_ytop - squares->sq_size) / 2;
	if (bottom >= area.r_ybot) nUp = 1;
    }
    else
	bottom = (area.r_ybot + area.r_ytop + squares->sq_sep
		- (nUp * pitch)) / 2;

    /* Lower-left coordinate should be centered on the contact cut, as
     * contact definitions are centered on the origin.
     */
    halfsize = (squares->sq_size / 2);
    left += halfsize;
    bottom += halfsize;

    result = CalmaGenerateArray((FILE *)csi->csi_client, csi->csi_type,
		left, bottom, pitch, nAcross, nUp);

    return (result == TRUE) ? 0 : 1;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSlotFunc --
 *
 * 	Called for each relevant tile area when chopping areas up into
 *	slots (rectangles).  Determines how to divide up the area into
 *	slots, and generates the number of rows, columns, and the lower-
 *	left-most cut rectangle.
 *
 * Results:
 *	Always return 0
 *
 * Side effects:
 *	Pointers "rows", "columns", and "cut" are filled with
 *	appropriate values.
 *
 * ----------------------------------------------------------------------------
 */

int
cifSlotFunc(area, op, numY, numX, cut, vertical)
    Rect  *area;		/* Area to be diced up			*/
    CIFOp *op;			/* Describes how to generate squares.	*/
    int *numY, *numX;		/* Return values: # rows and # columns 	*/
    Rect *cut;			/* initial (lower left) cut area 	*/
    bool vertical;		/* if TRUE, slot is aligned vertically	*/
{
    int i, j, xpitch, ypitch, delta, limit;
    int *axtop, *axbot, *aytop, *aybot;
    int *sxtop, *sxbot, *sytop, *sybot;
    int *rows, *columns;
    SlotsData *slots = (SlotsData *)op->co_client;

    /* Orient to the short/long orientation of the tile */

    /* Assume a vertical tile;  if not, reorient area and remember */
    if (vertical)
    {
	axbot = &area->r_xbot;
	aybot = &area->r_ybot;
	axtop = &area->r_xtop;
	aytop = &area->r_ytop;
	sxbot = &cut->r_xbot;
	sybot = &cut->r_ybot;
	sxtop = &cut->r_xtop;
	sytop = &cut->r_ytop;
	rows = numY;
	columns = numX;
    }
    else
    {
	axbot = &area->r_ybot;
	aybot = &area->r_xbot;
	axtop = &area->r_ytop;
	aytop = &area->r_xtop;
	sxbot = &cut->r_ybot;
	sybot = &cut->r_xbot;
	sxtop = &cut->r_ytop;
	sytop = &cut->r_xtop;
	rows = numX;
	columns = numY;
    }

    xpitch = slots->sl_ssize + slots->sl_ssep;

calcX:
    *columns = (*axtop - *axbot + slots->sl_ssep - (2 * slots->sl_sborder)) / xpitch;
    if (*columns == 0)
    {
	*rows = 0;
	return 0;
	// *sxbot = (*axbot + *axtop - slots->sl_ssize) / 2;
	// if (*sxbot >= *axbot) *columns = 1;
    }
    else
	*sxbot = (*axbot + *axtop + slots->sl_ssep - (*columns * xpitch)) / 2;
    *sxtop = *sxbot + slots->sl_ssize;

    /* Check that we are not violating any gridlimit */

    limit = CIFCurStyle->cs_gridLimit * CIFCurStyle->cs_expander;
    limit /= (CIFCurStyle->cs_flags & CWF_ANGSTROMS) ? 100 : 10;

    if (CIFCurStyle && (limit > 1))
    {
	delta = abs(*sxbot) % limit;
	if (delta > 0)
	{
	    if (*sxbot >= 0)
		*axtop -= 2 * delta;
	    else
		*axtop += 2 * delta;
	    goto calcX;
	}
    }

    if (slots->sl_lsize > 0)
    {
	ypitch = slots->sl_lsize + slots->sl_lsep;
calcY:
	*rows = (*aytop - *aybot + slots->sl_lsep - (2 * slots->sl_lborder)) / ypitch;
	if (*rows == 0)
	{
	    return 0;
	    // *sybot = (*aybot + *aytop - slots->sl_lsize) / 2;
	    // if (*sybot >= *aybot) *rows = 1;
	}
	else
	    *sybot = (*aybot + *aytop + slots->sl_lsep - (*rows * ypitch)) / 2;
	*sytop = *sybot + slots->sl_lsize;

	/* Check that we are not violating any gridlimit */

	if (CIFCurStyle && (limit > 1))
	{
	    delta = abs(*sybot) % limit;
	    if (delta > 0)
	    {
		if (*sybot >= 0)
		    *aytop -= 2 * delta;
		else
		    *aytop += 2 * delta;
		goto calcY;
	    }
	}
    }
    else
    {
	*rows = 1;
	*sybot = *aybot + slots->sl_lborder;
	*sytop = *aytop - slots->sl_lborder;
	/* There's no space to fit a slot */
	if (*sytop - *sybot <= 0)
	    return 0;
    }

    /* To be done---slot offsets */

    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquareFunc --
 *
 * 	Called for each relevant rectangle when chopping areas up into
 *	squares.   Determines the number of rows and columns in the area
 *	and returns these and the area of the lower-left cut.
 *
 * Results:
 *	Always return 0
 *
 * Side effects:
 *	Results filled in the pointer positions passed to the function
 *
 * ----------------------------------------------------------------------------
 */

int
cifSquareFunc(area, op, rows, columns, cut)
    Rect *area;			/* Area to be diced up */
    CIFOp *op;			/* Describes how to generate squares.	*/
    int *rows, *columns;	/* Return values: # rows and # columns,	*/
    Rect *cut;			/* initial (lower left) cut area.	*/
{
    int pitch, delta, limit;
    bool glimit;
    SquaresData *squares = (SquaresData *)op->co_client;

    limit = CIFCurStyle->cs_gridLimit * CIFCurStyle->cs_expander;
    limit /= (CIFCurStyle->cs_flags & CWF_ANGSTROMS) ? 100 : 10;

    glimit = (CIFCurStyle && (limit > 1)) ? TRUE : FALSE;
    pitch = squares->sq_size + squares->sq_sep;

    /* Compute the real border to leave around the sides.  If only
     * one square will fit in a particular direction, center it
     * regardless of the requested border size.  If more than one
     * square will fit, then fit it in extras only if at least the
     * requested border size can be left.  Also center things in the
     * rectangle, so that the box's exact size doesn't matter. This
     * trickiness is done so that coincident contacts from overlapping
     * cells always have their squares line up, regardless of the
     * orientation of the cells.
     *
     * Update 1/13/09:  Removed the "feature" that allows contact
     * cuts that violate the border requirement.  The "slots" rule
     * can be used if necessary to generate cuts with different
     * border allowances.
     */

sqX:
    *columns = (area->r_xtop - area->r_xbot + squares->sq_sep
	    - (2 * squares->sq_border)) / pitch;
    if (*columns == 0)
    {
	*rows = 0;
	return 0;

	// cut->r_xbot = (area->r_xbot + area->r_xtop - squares->sq_size) / 2;
	// if (cut->r_xbot >= area->r_xbot) *columns = 1;
    }
    else
    {
	cut->r_xbot = (area->r_xbot + area->r_xtop + squares->sq_sep
		- (*columns * pitch)) / 2;
    }

    /* Check for any gridlimit violation */

    if (glimit)
    {
	delta = abs(cut->r_xbot) % limit;
	if (delta > 0)
	{
	    area->r_xtop -= 2 * delta;
	    goto sqX;
	}
    }

sqY:
    *rows = (area->r_ytop - area->r_ybot + squares->sq_sep
	    - (2 * squares->sq_border)) / pitch;
    if (*rows == 0)
    {
	return 0;

	// cut->r_ybot = (area->r_ybot + area->r_ytop - squares->sq_size) / 2;
	// if (cut->r_ybot >= area->r_ybot) *rows = 1;
    }
    else
    {
	cut->r_ybot = (area->r_ybot + area->r_ytop + squares->sq_sep
		- (*rows * pitch)) / 2;
    }

    /* Check for any gridlimit violation */

    if (glimit)
    {
	delta = abs(cut->r_ybot) % limit;
	if (delta > 0)
	{
	    area->r_ytop -= 2 * delta;
	    goto sqY;
	}
    }

    cut->r_xtop = cut->r_xbot + squares->sq_size;
    cut->r_ytop = cut->r_ybot + squares->sq_size;
    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifSquareGridFunc --
 *
 * 	Called for each relevant rectangle when chopping areas up into
 *	squares.   Determines the number of rows and columns in the area
 *	and returns these and the area of the lower-left cut.
 *
 * Results:
 *	Always return 0
 *
 * Side effects:
 *	Results filled in the pointer positions passed to the function
 *
 * ----------------------------------------------------------------------------
 */

int
cifSquareGridFunc(area, op, rows, columns, cut)
    Rect *area;			/* Area to be diced up */
    CIFOp *op;			/* Describes how to generate squares.	*/
    int *rows, *columns;	/* Return values: # rows and # columns,	*/
    Rect *cut;			/* initial (lower left) cut area.	*/
{
    Rect locarea;
    int left, bottom, right, top, pitch;
    int gridx, gridy, margin;
    SquaresData *squares = (SquaresData *)op->co_client;

    /*
     * It may be necessary to generate contacts on a specific grid; e.g.,
     * to avoid placing contacts at half-lambda.  If this is the case,
     * then the DRC section of the techfile should specify "no overlap"
     * for these types.
     *
     * This routine has been simplified.  It flags a warning when there
     * is not enough space for a contact cut, rather than attempting to
     * draw a cut without enough border area.  The routine has also been
     * extended to allow different x and y grids to be specified.  This
     * allows certain tricks, such as generating offset contact grids on
     * a pad, as required by some processes.
     */

    pitch = squares->sq_size + squares->sq_sep;
    gridx = squares->sq_gridx;
    gridy = squares->sq_gridy;

    locarea.r_xtop = area->r_xtop - squares->sq_border;
    locarea.r_ytop = area->r_ytop - squares->sq_border;
    locarea.r_xbot = area->r_xbot + squares->sq_border;
    locarea.r_ybot = area->r_ybot + squares->sq_border;

    left = locarea.r_xbot / gridx;
    left *= gridx;
    if (left < locarea.r_xbot) left += gridx;

    bottom = locarea.r_ybot / gridy;
    bottom *= gridy;
    if (bottom < locarea.r_ybot) bottom += gridy;

    *columns = (locarea.r_xtop - left + squares->sq_sep) / pitch;
    if (*columns == 0)
    {
	*rows = 0;
	return 0;
    }

    *rows = (locarea.r_ytop - bottom + squares->sq_sep) / pitch;
    if (*rows == 0) return 0;

    /* Center the contacts while remaining on-grid */
    right = left + *columns * squares->sq_size + (*columns - 1) * squares->sq_sep;
    top = bottom + *rows * squares->sq_size + (*rows - 1) * squares->sq_sep;
    margin = ((locarea.r_xtop - right) - (left - locarea.r_xbot)) / (gridx * 2);
    locarea.r_xbot = left + margin * gridx;
    margin = ((locarea.r_ytop - top) - (bottom - locarea.r_ybot)) / (gridy * 2);
    locarea.r_ybot = bottom + margin * gridy;

    cut->r_ybot = locarea.r_ybot;
    cut->r_ytop = cut->r_ybot + squares->sq_size;
    cut->r_xbot = locarea.r_xbot;
    cut->r_xtop = cut->r_xbot + squares->sq_size;
    return 0;
}


/*
 * ----------------------------------------------------------------------------
 *
 * cifSrTiles --
 *
 * 	This is a utility procedure that just calls DBSrPaintArea
 *	one or more times for the planes being used in processing
 *	one CIFOp.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	This procedure itself has no side effects.  For each of the
 *	paint or temporary planes indicated in cifOp, we call
 *	DBSrPaintArea to find the desired tiles in the desired
 *	area for the operation.  DBSrPaintArea is given func as a
 *	search function, and cdArg as ClientData.
 *
 * ----------------------------------------------------------------------------
 */

void
cifSrTiles(cifOp, area, cellDef, temps, func, cdArg)
    CIFOp *cifOp;		/* Geometric operation being processed. */
    Rect *area;			/* Area of Magic paint to consider. */
    CellDef *cellDef;		/* CellDef to search for paint. */
    Plane *temps[];		/* Planes to use for temporaries. */
    int (*func)();		/* Search function to pass to DBSrPaintArea. */
    ClientData cdArg;		/* Client data for func. */
{
    TileTypeBitMask maskBits;
    TileType t;
    Tile *tp;
    int i;
    BloatData *bloats;

    /* When reading data from a cell, it must first be scaled to
     * CIF units.  Check for CIFCurStyle, as we don't want to
     * crash while reading CIF/GDS just becuase the techfile
     * "cifoutput" section was blank.
     */

    cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;

    /* Bloat operations (except bloat-all) have to be in a single plane */

    switch (cifOp->co_opcode) {
	case CIFOP_BLOAT:
	case CIFOP_BLOATMIN:
	case CIFOP_BLOATMAX:
	    bloats = (BloatData *)cifOp->co_client;
	    i = bloats->bl_plane;
	    maskBits = DBPlaneTypes[i];
	    TTMaskAndMask(&maskBits, &cifOp->co_paintMask);
	    if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
		DBSrPaintArea((Tile *) NULL, cellDef->cd_planes[i],
				area, &cifOp->co_paintMask, func, cdArg);
	    break;

	default:
	    for (i = PL_DRC_CHECK; i < DBNumPlanes; i++)
	    {
		maskBits = DBPlaneTypes[i];
		TTMaskAndMask(&maskBits, &cifOp->co_paintMask);
		if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
		    (void) DBSrPaintArea((Tile *) NULL, cellDef->cd_planes[i],
			area, &cifOp->co_paintMask, func, cdArg);
	    }
	    break;
    }

    /* When processing CIF data, use everything in the plane. */

    cifScale = 1;
    for (t = 0; t < TT_MAXTYPES; t++, temps++)
	if (TTMaskHasType(&cifOp->co_cifMask, t))
	    (void) DBSrPaintArea((Tile *) NULL, *temps, &TiPlaneRect,
		&CIFSolidBits, func, (ClientData) cdArg);
}

/* Data structure to pass plane and minimum width to the callback function */
typedef struct _bridgeLimStruct {
    Plane       *plane;
    BridgeData	*bridge;
    CellDef     *def;
    Plane       **temps;
    TileTypeBitMask co_paintMask;/* Zero or more paint layers to consider. */
    TileTypeBitMask co_cifMask;  /* Zero or more other CIF layers. */
} BridgeLimStruct;

static int xOverlap, yOverlap;

/* Bridge-lim Check data structure */
typedef struct _bridgeLimCheckStruct {
   Tile *tile;		/* Tile that triggered search (ignore this tile) */
   int	direction;	/* What outside corner to look for */
   Tile *violator;	/* Return the violator tile in this space */
   TileType checktype;	/* Type to check for, either TT_SPACE or CIF_SOLIDTYPE */
   long sqdistance;     /* Square of the minimum distance */
} BridgeLimCheckStruct;
/*
 *-----------------------------------------------------------------------
 * Callback function for bridgeLimSrTiles used when a limiting layer tile
 * was found in the specified area. If calcOverlap is TRUE then the xOverlap
 * and yOverlap are updated and return 0 to continue searching. Otherwise
 * return 1 to stop the search.
 *-----------------------------------------------------------------------
 */
int
bridgeLimFound(tile, calcOverlap)
    Tile *tile;
    bool calcOverlap;
{
    if (calcOverlap)
    {
        if (RIGHT(tile) > xOverlap)
                xOverlap = RIGHT(tile);
        if (TOP(tile) > yOverlap)
                yOverlap = TOP(tile);
        return 0;       // continue searching
    } else
        return 1;       // tile found, stop the search
}

/*
 *------------------------------------------------------------------------
 * Callback function used in bridge-lim operations to find if the specified
 * area contains tiles of the limiting layers.
 *------------------------------------------------------------------------
 */
int
bridgeLimSrTiles(brlims, area, calcOverlap)
    BridgeLimStruct *brlims;    /* Bridge-Lim structure. */
    Rect *area;                 /* Area of Magic paint to consider. */
    bool calcOverlap;           /* TRUE to calculate the overlap of the limiting tiles in the specified area. */
{
    TileTypeBitMask maskBits;
    TileType t;
    int i;
    Plane **temps = brlims->temps;
    xOverlap = area->r_xbot;
    yOverlap = area->r_ybot;

    for (i = PL_DRC_CHECK; i < DBNumPlanes; i++)
    {
	maskBits = DBPlaneTypes[i];
	TTMaskAndMask(&maskBits, &brlims->co_paintMask);
	if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
	    if (DBSrPaintArea((Tile *) NULL, brlims->def->cd_planes[i], area, &brlims->co_paintMask, bridgeLimFound, calcOverlap))
		return 0;
    }

    for (t = 0; t < TT_MAXTYPES; t++, temps++)
        if (TTMaskHasType(&brlims->co_cifMask, t))
           if (DBSrPaintArea((Tile *) NULL, *temps, area, &CIFSolidBits, bridgeLimFound, calcOverlap))
                return 0;

    if (( xOverlap != area->r_xbot) || (yOverlap != area->r_ybot))
        return 0;       //Constraint tile found
    else
        return 1;       //Nothing found
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBridgeLimFunc0 --
 *
 * 	Called for each relevant tile during bridge-lim operations.  The
 *	bridge-lim operation is similar to the bridge operation with the
 *	difference that the material created to meet the minimum spacing/width
 *	rules do not overlap the limiting layers.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	May paint into cifNewPlane
 *
 * Algorithm (based on maximum horizontal stripes rule):
 * This function grows dimentions of tiles to meet a minimimum width rule (only
 * applies to vertical or horizontal directions). This is done in two steps:
 * 	1. Adjust tile width to accomplish the minimimum width rule, limited by
 *	the constraint layers.
 *	2. Search top and bottom tiles of same type, for each segment verify if
 *	height meets the minimimum value, if not, adjust the segment height
 *	but do not paint over limiting layer tiles.
 * ----------------------------------------------------------------------------
 */
int
cifBridgeLimFunc0(tile, brlims)
    Tile *tile;
    BridgeLimStruct *brlims;
{
    Plane *plane = brlims->plane;
    Rect area, parea;
    int minDistance = brlims->bridge->br_width;
    int width, height, ybot0, tp2lim;
    Tile *tp, *tp2;

    TiToRect(tile, &area);

    /* Check whole tile for minimum width */
    width = area.r_xtop - area.r_xbot;
    if (width < minDistance)
    {
	area.r_xbot = area.r_xtop - minDistance;
        if (!bridgeLimSrTiles(brlims, &area, TRUE))
	{
            area.r_xbot = MIN(LEFT(tile), xOverlap);
	    area.r_xtop = area.r_xbot + minDistance;
	}
    }

	/* If there is another tile on top or bottom, and the height is	*/
	/* less than minimum, then extend height in the direction of	*/
	/* the bordering tile.  Otherwise, if the height is less than	*/
	/* minimum, then grow considering the limiting layers.	*/

	height = area.r_ytop - area.r_ybot;
	if (height < minDistance)
	{
         for (tp = LB(tile); LEFT(tp) < RIGHT(tile); tp = TR(tp))
            {
            tp2lim = MAX(LEFT(tp), area.r_xbot);
            for (tp2 = RT(tile); RIGHT(tp2) > tp2lim; tp2 = BL(tp2))
                if (LEFT(tp2) < RIGHT(tp))
                {
                   parea.r_xbot = MAX(LEFT(tp2), tp2lim);
                   parea.r_xtop = MIN(MIN(RIGHT(tp2), RIGHT(tp)), area.r_xtop);
                   if (TiGetBottomType(tp2) == TiGetTopType(tile))
                        parea.r_ytop = TOP(tp2);
                   else
                        parea.r_ytop = area.r_ytop;
                   if (TiGetTopType(tp) == TiGetBottomType(tile))
                        ybot0 = BOTTOM(tp);
                   else
                        ybot0 = area.r_ybot;
                   height = parea.r_ytop - ybot0;
                   if (height < minDistance)
                   {
                        parea.r_ybot = parea.r_ytop - minDistance;
                        if (!bridgeLimSrTiles(brlims, &parea, TRUE))
                        {
                           parea.r_ybot = MIN(ybot0 , yOverlap);
                           parea.r_ytop = parea.r_ybot + minDistance;
                        }
                        DBPaintPlane(cifPlane, &parea, CIFPaintTable, (PaintUndoInfo *) NULL);
                   }
                }
            }
        }
    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
    return 0;
}

/*
 *-----------------------------------------------------------------------
 * Callback function for cifBridgeLimFunc1 and cifBridgeLimFunc2 to find if
 * there are violator cells in the search area.	 If a violator cell is
 * found, then put the tile pointer in the BridgeCheckStruct and return
 * value 1 to stop the search.	Otherwise return 0 to keep going.
 *-----------------------------------------------------------------------
 */
int
bridgeLimCheckFunc(tile, brlimcs)
    Tile *tile;
    BridgeLimCheckStruct *brlimcs;
{
    int dir = brlimcs->direction;
    Tile *self = brlimcs->tile;
    Tile *tp1, *tp2;
    TileType checktype = brlimcs->checktype;
    long sqdistance = brlimcs->sqdistance;
    int dx, dy;
    long sqcheck;

    if (self == tile) return 0;	    /* Ignore the triggering tile */

    switch (dir) {
	case BRIDGE_NW:
	    /* Ignore tile if split, and SE corner is clipped */
	    if (IsSplit(tile))
	    if (TiGetRightType(tile) == checktype || TiGetBottomType(tile) == checktype)
		break;
	    for (tp1 = RT(tile); LEFT(tp1) > LEFT(tile); tp1 = BL(tp1));
	    for (tp2 = BL(tile); TOP(tp2) < TOP(tile); tp2 = RT(tp2));
	    if ((TiGetBottomType(tp1) == checktype) &&
		    (TiGetRightType(tp2) == checktype))
	    {
		dx = LEFT(tile) - RIGHT(self);
		dy = BOTTOM(self) - TOP(tile);
		if ((dx > 0) && (dy > 0))
		{
		   sqcheck = (long)dx*dx + (long)dy*dy; 
		   if (sqcheck >= sqdistance)
			return 0;
		}
		brlimcs->violator = tile;
		return 1;	/* Violator found */
	    }
	    break;
	case BRIDGE_SW:
	    /* Ignore tile if split, and NE corner is clipped */
	    if (IsSplit(tile))
	    if (TiGetRightType(tile) == checktype || TiGetTopType(tile) == checktype)
		break;
	    tp1 = LB(tile);
	    tp2 = BL(tile);
	    if ((TiGetTopType(tp1) == checktype) &&
		    (TiGetRightType(tp2) == checktype))
	    {
		dx = LEFT(tile) - RIGHT(self);
		dy = BOTTOM(tile) - TOP(self);
		if ((dx > 0) && (dy > 0))
		{
		   sqcheck = (long)dx*dx + (long)dy*dy; 
		   if (sqcheck >= sqdistance)
			return 0;
		}
		brlimcs->violator = tile;
		return 1;	/* Violator found */
	    }
	    break;
    }
    return 0;	/* Nothing found here, so keep going */
}

/*
 *-----------------------------------------------------------------------
 * Callback function used in bridge-lim operations to do not paint areas 
 * where new bridge overlaps the limiting layer tiles.
 *-----------------------------------------------------------------------
 */
int
bridgeErase(brlims, area)
    BridgeLimStruct *brlims;    /* Bridge-lim structure. */
    Rect *area;                 /* Area of Magic paint to consider. */
{
    TileTypeBitMask maskBits;
    TileType t;
    int i;
    Plane **temps = brlims->temps;

    for (i = PL_DRC_CHECK; i < DBNumPlanes; i++)
    {
	maskBits = DBPlaneTypes[i];
	TTMaskAndMask(&maskBits, &brlims->co_paintMask);
	if (!TTMaskEqual(&maskBits, &DBZeroTypeBits))
	    if (DBSrPaintArea((Tile *) NULL, brlims->def->cd_planes[i], area, &brlims->co_paintMask, cifPaintFunc, CIFEraseTable))
		return 0;
    }

    for (t = 0; t < TT_MAXTYPES; t++, temps++)
        if (TTMaskHasType(&brlims->co_cifMask, t))
           if (DBSrPaintArea((Tile *) NULL, *temps, area, &CIFSolidBits, cifPaintFunc, CIFEraseTable))
                return 0;
	
        return 1;       //Nothing found
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifBridgeLimFunc1 --
 *
 * 	Called for each relevant tile during bridge-lim operations.  The
 *	bridge-lim operation is similar to the bridge operation with the
 *	difference that the material created to meet the minimum spacing/width
 *	rules do not overlap the limiting layers.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	May paint into cifNewPlane
 * ----------------------------------------------------------------------------
 */
int
cifBridgeLimFunc1(tile, brlims)
    Tile *tile;
    BridgeLimStruct *brlims;
{
    Plane *plane = brlims->plane;
    Rect area;
    Tile *tp1, *tp2, *tpx;
    int width = brlims->bridge->br_width;
    int spacing = growDistance;
    BridgeLimCheckStruct brlimcs;
    brlimcs.sqdistance = (long) spacing * spacing;

    /* If tile is marked, then it has been handled, so ignore it */
    if (tile->ti_client != (ClientData)CIF_UNPROCESSED) return 0;

    /* Find each tile outside corner (up to four) */

    /* Check for NE outside corner */
    tp1 = TR(tile);  /* Tile on right side at the top of this tile */
    tp2 = RT(tile);  /* Tile on top side at the right of this tile */
    if ((TiGetLeftType(tp1) == TT_SPACE) &&
	    (TiGetBottomType(tp2) == TT_SPACE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile);
	area.r_xtop = RIGHT(tile) + spacing;
	area.r_ybot = TOP(tile);
	area.r_ytop = TOP(tile) + spacing;

	/* Find violator tiles */
	brlimcs.tile = tile;
	brlimcs.direction = BRIDGE_SW;
	brlimcs.checktype = TT_SPACE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &CIFSolidBits, bridgeLimCheckFunc, (ClientData)&brlimcs) == 1)
	{
	    tpx = brlimcs.violator;
	    area.r_xtop = MAX(RIGHT(tile), LEFT(tpx) + width);
	    area.r_ytop = MAX(TOP(tile), BOTTOM(tpx));
	    area.r_xbot = MIN(LEFT(tpx), RIGHT(tile));
	    area.r_ybot = MIN(BOTTOM(tpx), TOP(tile) - width);
	    if (bridgeLimSrTiles(brlims, &area, FALSE))
	    {
		/* First option of bridge can be implemented (there are not limiting tiles in the area)*/
		area.r_ytop = TOP(tile);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
		area.r_xbot = LEFT(tpx);
		area.r_ytop = MAX(TOP(tile), BOTTOM(tpx));
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    }
	    else
	    {
	    area.r_xtop = MAX(RIGHT(tile), LEFT(tpx));
	    area.r_ytop = MAX(TOP(tile), BOTTOM(tpx) + width);
	    area.r_xbot = MIN(LEFT(tpx), RIGHT(tile) - width);
	    area.r_ybot = MIN(BOTTOM(tpx), TOP(tile));
	    if (bridgeLimSrTiles(brlims, &area, FALSE))
		{
		/* Second option of bridge can be implemented (there are not limiting tiles in the area)*/
		area.r_ybot = BOTTOM(tpx);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
		area.r_xtop = RIGHT(tile);
	    	area.r_ybot = MIN(BOTTOM(tpx), TOP(tile));
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
		}
		else
		{
		/* Last option (Limiting tiles are present on both sides, those areas must be excluded from the bridge)*/
	    	area.r_xtop = MAX(RIGHT(tile), LEFT(tpx) + width);
	    	area.r_ytop = MAX(TOP(tile), BOTTOM(tpx) + width);
	    	area.r_xbot = MIN(LEFT(tpx), RIGHT(tile) - width);
	    	area.r_ybot = MIN(BOTTOM(tpx), TOP(tile) - width);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    	bridgeErase(brlims, &area);
		}
	    }
	}
    }

    /* Check for SE outside corner */
    for (tp1 = TR(tile); BOTTOM(tp1) > BOTTOM(tile); tp1 = LB(tp1));
    for (tp2 = LB(tile); RIGHT(tp1) < RIGHT(tile); tp2 = TR(tp2));
    if ((TiGetLeftType(tp1) == TT_SPACE) &&
	    (TiGetTopType(tp2) == TT_SPACE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile);
	area.r_xtop = RIGHT(tile) + spacing;
	area.r_ybot = BOTTOM(tile) - spacing;
	area.r_ytop = BOTTOM(tile);

	/* Find violator tiles */
	brlimcs.tile = tile;
	brlimcs.direction = BRIDGE_NW;
	brlimcs.checktype = TT_SPACE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &CIFSolidBits, bridgeLimCheckFunc, (ClientData)&brlimcs) == 1)
	{
	    tpx = brlimcs.violator;
	    area.r_xtop = MAX(RIGHT(tile), LEFT(tpx));
	    area.r_ybot = MIN(BOTTOM(tile), TOP(tpx) - width);
	    area.r_xbot = MIN(LEFT(tpx), RIGHT(tile) - width);
	    area.r_ytop = MAX(TOP(tpx), BOTTOM(tile));
	    if (bridgeLimSrTiles(brlims, &area, FALSE))
	    {
		/* First option of bridge can be implemented (there are not limiting tiles in the area)*/
		area.r_xtop = RIGHT(tile);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    	area.r_xtop = MAX(RIGHT(tile), LEFT(tpx));
		area.r_ytop = TOP(tpx);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    }
	    else
	    {
	    area.r_xtop = MAX(RIGHT(tile), LEFT(tpx) + width);
	    area.r_ybot = MIN(BOTTOM(tile), TOP(tpx));
	    area.r_xbot = MIN(LEFT(tpx), RIGHT(tile));
	    area.r_ytop = MAX(TOP(tpx), BOTTOM(tile) + width);
	    if (bridgeLimSrTiles(brlims, &area, FALSE))
		{
		/* Second option of bridge can be implemented (there are not limiting tiles in the area)*/
		area.r_xbot = LEFT(tpx);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    	area.r_xbot = MIN(LEFT(tpx), RIGHT(tile));
		area.r_ybot = BOTTOM(tile);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
		}
		else
		{
		/* Last option (Limiting tiles are present on both sides, those areas must be excluded from the bridge)*/
		area.r_xtop = MAX(RIGHT(tile), LEFT(tpx) + width);
		area.r_ybot = MIN(BOTTOM(tile), TOP(tpx) - width);
		area.r_xbot = MIN(LEFT(tpx), RIGHT(tile) - width);
		area.r_ytop = MAX(TOP(tpx), BOTTOM(tile) + width);
		DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    	bridgeErase(brlims, &area);
		}
	    }
	}
    }

    return 0;
}

/*
 * ----------------------------------------------------------------------------
 * cifBridgeLimFunc2 --
 *
 * 	Called for each relevant tile during bridge-lim operations.  The
 *	bridge-lim operation is similar to the bridge operation with the
 *	difference that the material created to meet the minimum spacing/width
 *	rules do not overlap the limiting layers.
 *
 * Results:
 *	Always returns 0 to keep the search alive.
 *
 * Side effects:
 *	May paint into cifNewPlane
 * ----------------------------------------------------------------------------
 */
int
cifBridgeLimFunc2(tile, brlims)
    Tile *tile;
    BridgeLimStruct *brlims;
{
    Plane *plane = brlims->plane;
    Rect area;
    Tile *tp1, *tp2, *tpx;
    int width = brlims->bridge->br_width;
    int thirdOption;
    int spacing = growDistance;
    BridgeLimCheckStruct brlimcs;
    brlimcs.sqdistance = (long) width * width;

    /* If tile is marked, then it has been handled, so ignore it */
    if (tile->ti_client != (ClientData)CIF_UNPROCESSED) return 0;

    /* Find each tile outside corner (up to four) */

    /* Check for NE outside corner */
    tp1 = TR(tile);  /* Tile on right side at the top of this tile */
    tp2 = RT(tile);  /* Tile on top side at the right of this tile */
    if ((TiGetLeftType(tp1) == CIF_SOLIDTYPE) &&
	    (TiGetBottomType(tp2) == CIF_SOLIDTYPE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile);
	area.r_xtop = RIGHT(tile) + width;
	area.r_ybot = TOP(tile);
	area.r_ytop = TOP(tile) + width;

	/* Find violator tiles */
	brlimcs.tile = tile;
	brlimcs.direction = BRIDGE_SW;
	brlimcs.checktype = CIF_SOLIDTYPE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &DBSpaceBits, bridgeLimCheckFunc, (ClientData)&brlimcs) == 1)
	{
	    tpx = brlimcs.violator;
	    area.r_xtop = RIGHT(tile);
	    area.r_ytop = TOP(tile);
	    area.r_xbot = LEFT(tpx) - width;
	    area.r_ybot = BOTTOM(tpx) - width;

	    thirdOption = 0;
	    if (!bridgeLimSrTiles(brlims, &area, FALSE))
	    {
	    	area.r_xtop = RIGHT(tile) + width;
	    	area.r_ytop = TOP(tile) + width;
	    	area.r_xbot = LEFT(tpx);
	    	area.r_ybot = BOTTOM(tpx);
	        if (!bridgeLimSrTiles(brlims, &area, FALSE))
		{
	    	   area.r_xbot = LEFT(tpx) - width;
		   area.r_ybot = BOTTOM(tpx) - width;
	    	   thirdOption = 1;
		}
	    }
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    if (thirdOption)
	    	bridgeErase(brlims, &area);
	}
    }

    /* Check for SE outside corner */
    for (tp1 = TR(tile); BOTTOM(tp1) > BOTTOM(tile); tp1 = LB(tp1));
    for (tp2 = LB(tile); RIGHT(tp2) < RIGHT(tile); tp2 = TR(tp2));
    if ((TiGetLeftType(tp1) == CIF_SOLIDTYPE) &&
	    (TiGetTopType(tp2) == CIF_SOLIDTYPE))
    {
	/* Set search box */
	area.r_xbot = RIGHT(tile);
	area.r_xtop = RIGHT(tile) + width;
	area.r_ybot = BOTTOM(tile) - width;
	area.r_ytop = BOTTOM(tile);

	/* Find violator tiles */
	brlimcs.tile = tile;
	brlimcs.direction = BRIDGE_NW;
	brlimcs.checktype = CIF_SOLIDTYPE;
	if (DBSrPaintArea((Tile *) NULL, plane, &area,
		    &DBSpaceBits, bridgeLimCheckFunc, (ClientData)&brlimcs) == 1)
	{
	    tpx = brlimcs.violator;
	    area.r_xtop = RIGHT(tile) + width;
	    area.r_ytop = TOP(tpx);
	    area.r_xbot = LEFT(tpx);
	    area.r_ybot = BOTTOM(tile) - width;

	    thirdOption = 0;
	    if (!bridgeLimSrTiles(brlims, &area, FALSE))
	    {
	    	area.r_xtop = RIGHT(tile);
	    	area.r_ytop = TOP(tpx) + width;
	    	area.r_xbot = LEFT(tpx) - width;
	    	area.r_ybot = BOTTOM(tile);
	        if (!bridgeLimSrTiles(brlims, &area, FALSE))
		{
	    	   area.r_xtop = RIGHT(tile) + width;
		   area.r_ybot = BOTTOM(tile) - width;
	    	   thirdOption = 1;
		}
	    }
	    DBPaintPlane(cifPlane, &area, CIFPaintTable, (PaintUndoInfo *) NULL);
	    if (thirdOption)
	    	bridgeErase(brlims, &area);
	}
    }

    return 0;
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFGenLayer --
 *
 *	This routine will generate one CIF layer.
 *	It provides the core of the CIF generator.
 *
 * Results:
 *	Returns a malloc'ed plane with tiles of type CIF_SOLIDTYPE
 *	marking the area of this CIF layer as built up by op.
 *
 * Side effects:
 *	None, except to create a new plane holding the CIF for the layer.
 *	The CIF that's generated may fall outside of area... it's what
 *	results from considering everything in area.  In most cases the
 *	caller will clip the results down to the desired area.
 *
 * ----------------------------------------------------------------------------
 */

Plane *
CIFGenLayer(op, area, cellDef, origDef, temps, hier, clientdata)
    CIFOp *op;			/* List of CIFOps telling how to make layer. */
    Rect *area;			/* Area to consider when generating CIF.  Only
				 * material in this area will be considered, so
				 * the caller should usually expand his desired
				 * area by one CIF radius.
				 */
    CellDef *cellDef;		/* CellDef to search when paint layers are
				 * needed for operation.
				 */
    CellDef *origDef;		/* Original CellDef for which output is being
				 * generated (cellDef may be derived from this).
				 */
    Plane *temps[];		/* Temporary layers to be used when needed
				 * for operation.
				 */
    bool hier;			/* TRUE if called from CIFGenSubcells or CIFGenArrays */
    ClientData clientdata;	/*
				 * Data that may be passed to the CIF operation
				 * function.
				 */
{
    Plane *temp;
    static Plane *nextPlane, *curPlane;
    Rect bbox;
    CIFOp *tempOp;
    CIFSquaresInfo csi;
    SearchContext scx;
    TileType ttype;
    char *netname;
    BloatStruct bls;
    BridgeStruct brs;
    BridgeLimStruct brlims;
    BridgeData *bridge;
    BloatData *bloats;
    bool hstop = FALSE;
    char *propvalue;
    bool found;

    int (*cifGrowFuncPtr)() = (CIFCurStyle->cs_flags & CWF_GROW_EUCLIDEAN) ?
		cifGrowEuclideanFunc : cifGrowFunc;

    /* Set up temporary planes used during computation.  One of these
     * will be returned as the result (whichever is curPlane at the
     * end of the computation).  The other is saved for later use.
     */

    if (nextPlane == NULL)
	nextPlane = DBNewPlane((ClientData) TT_SPACE);
    curPlane = DBNewPlane((ClientData) TT_SPACE);

    /* Go through the geometric operations and process them one
     * at a time.
     *
     * NOTE:  Some opcodes (and whatever follows them) should never
     * be run during hierarchical processing.  That includes BOUNDARY,
     * SQUARES/SLOTS, BBOX, and NET.
     *
     * Caveat:  SQUARES/SLOTS followed by GROW can be used to define
     * an etch area around a contact;  this should be considered a
     * special case that requires hierarchical processing on SQUARES/
     * SLOTS.
     */

    for ( ; op != NULL; op = op->co_next)
    {
	switch (op->co_opcode)
	{
	    /* For AND, first collect all the stuff to be anded with
	     * plane in a temporary plane.  Then find all the places
	     * where there isn't any stuff, and erase from the
	     * current plane.
	     */

	    case CIFOP_AND:
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
		    (ClientData) CIFPaintTable);
		cifPlane = curPlane;
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, nextPlane, &TiPlaneRect,
		    &DBSpaceBits, cifPaintFunc,
		    (ClientData) CIFEraseTable);
		break;

	    /* For OR, just use cifPaintFunc to OR the areas of all
	     * relevant tiles into plane.  HOWEVER, if the co_client
	     * record is non-NULL and CalmaContactArrays is TRUE,
	     * then for each contact type, we do the paint function
	     * separately, then call the contact array generation
	     * procedure.
	     */

	    case CIFOP_OR:
		cifPlane = curPlane;
		cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;

		if ((op->co_client != (ClientData)NULL)
				&& (CalmaContactArrays == TRUE))
		{
		    TileTypeBitMask paintMask, errMask, *rMask;
		    TileType i, j;

		    TTMaskZero(&errMask);
		    TTMaskZero(&paintMask);
 		    TTMaskSetMask(&paintMask, &op->co_paintMask);
		    for (i = TT_TECHDEPBASE; i < DBNumUserLayers; i++)
		    {
			if (TTMaskHasType(&paintMask, i))
			{
			    TTMaskSetOnlyType(&op->co_paintMask, i);
			    for (j = DBNumUserLayers; j < DBNumTypes; j++)
			    {
				rMask = DBResidueMask(j);
				if (TTMaskHasType(rMask, i))
				    TTMaskSetType(&op->co_paintMask, j);
			    }

			    cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
			    		(ClientData) CIFPaintTable);

			    csi.csi_squares = (SquaresData *)op->co_client;
			    csi.csi_type = i;
			    csi.csi_client = clientdata;

			    if (DBSrPaintArea((Tile *) NULL, curPlane,
					&TiPlaneRect, &CIFSolidBits,
					cifContactFunc,	(ClientData) &csi))
			    {
				/* Failure of DBSrPaintArea() (returns 1)
				 * indicates that a contact cell type
				 * could not be found for magic layer i.
				 * Record the error for subsequent handling.
				 */
				TTMaskSetType(&errMask, i);
			    }
			    DBClearPaintPlane(curPlane);
			}
		    }
		    if (!TTMaskIsZero(&errMask))
		    {
			/*
			 * Handle layers for which a contact cell could
			 * not be found in the default manner.
			 */
			TTMaskZero(&op->co_paintMask);
 			TTMaskSetMask(&op->co_paintMask, &errMask);
			cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
		    		(ClientData) CIFPaintTable);
		    }

		    /* Recover the original magic layer mask for the cifop */

		    TTMaskZero(&op->co_paintMask);
 		    TTMaskSetMask(&op->co_paintMask, &paintMask);
		}
		else
		{
		    cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
		    	(ClientData) CIFPaintTable);
		}
		break;

	    /* For ANDNOT, do exactly the same thing as OR, except erase
	     * instead of paint.
	     */

	    case CIFOP_ANDNOT:
		cifPlane = curPlane;
		cifSrTiles(op, area, cellDef, temps, cifPaintFunc,
		    (ClientData) CIFEraseTable);
		break;

	    /* For GROW, just find all solid tiles in the current plane,
	     * and paint a larger version into a new plane.  The switch
	     * the current and new planes.
	     */

	    case CIFOP_GROW:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, *cifGrowFuncPtr, (ClientData) CIFPaintTable);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    /* GROWMIN grows non-uniformly to ensure minimum dimensions */

	    case CIFOP_GROWMIN:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifGrowMinFunc, (ClientData)CIFPaintTable);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    /* GROW_G grows non-uniformly to the indicated grid. */

	    case CIFOP_GROW_G:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifGrowGridFunc, (ClientData) CIFPaintTable);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    /* SHRINK is just like grow except work from the space tiles. */

	    case CIFOP_SHRINK:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		DBPaintPlane(nextPlane, &TiPlaneRect, CIFPaintTable,
		    (PaintUndoInfo *) NULL);
		cifPlane = nextPlane;
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &DBSpaceBits, *cifGrowFuncPtr, (ClientData) CIFEraseTable);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_CLOSE:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		/* First copy the existing paint into the target plane */
		DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    	&CIFSolidBits, cifPaintFunc, (ClientData)CIFPaintTable);
		DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    	&DBSpaceBits, cifCloseFunc, (ClientData)&curPlane);

		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_BRIDGE:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		/* First copy the existing paint into the target plane */
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifPaintFunc, (ClientData)CIFPaintTable);

		brs.plane = curPlane;
		brs.bridge = (BridgeData *)op->co_client;
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifBridgeFunc1, (ClientData)&brs);
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &DBSpaceBits, cifBridgeFunc2, (ClientData)&brs);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_BRIDGELIM:
		growDistance = op->co_distance;
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifScale = 1;
		
                brlims.bridge = (BridgeData *)op->co_client;
                brlims.def = cellDef;
                brlims.temps = temps;
		brlims.co_paintMask = op->co_paintMask;
		brlims.co_cifMask = op->co_cifMask;

		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifBridgeLimFunc0, (ClientData)&brlims);
		temp = curPlane;
                curPlane = nextPlane;
		brlims.plane = curPlane;

		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &CIFSolidBits, cifBridgeLimFunc1, (ClientData)&brlims);
		(void) DBSrPaintArea((Tile *) NULL, curPlane, &TiPlaneRect,
		    &DBSpaceBits, cifBridgeLimFunc2, (ClientData)&brlims);
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_BLOAT:
		cifPlane = curPlane;
		cifSrTiles(op, area, cellDef, temps,
		    cifBloatFunc, op->co_client);
		break;

	    case CIFOP_BLOATMAX:
	    case CIFOP_BLOATMIN:
		cifPlane = curPlane;
		cifSrTiles(op, area, cellDef, temps,
		    cifBloatMaxFunc, (ClientData) op);
		break;

	    case CIFOP_BLOATALL:
		cifPlane = curPlane;
		bls.op = op;
		bls.def = cellDef;
		bls.temps = temps;

	        /* Create a mask of all connecting types (these must be in a single
	         * plane), then call a search function to find all connecting material
	         * of these types (if the bloat types are temp layers, then this mask
	         * is not used).
	         */

	        bloats = (BloatData *)op->co_client;
	        if (bloats->bl_plane < 0)
	        {
		   /* bl_plane == -1 indicates bloating into a CIF templayer,	*/
		   /* so the only connecting type should be CIF_SOLIDTYPE.	*/
		   TTMaskSetOnlyType(&bls.connect, CIF_SOLIDTYPE);
	        }
	        else
	        {
		    int i;
		    TTMaskZero(&bls.connect);
		    for (i = 0; i < TT_MAXTYPES; i++)
			if (bloats->bl_distance[i] != 0)
			  TTMaskSetType(&bls.connect, i);
	        }

		cifSrTiles(op, area, cellDef, temps, cifBloatAllFunc, (ClientData)&bls);

	        /* Reset marked tiles */

	        if (bloats->bl_plane < 0)   /* Bloat types are CIF types */
	        {
		    bls.temps = temps;
		    for (ttype = 0; ttype < TT_MAXTYPES; ttype++, bls.temps++)
			if (bloats->bl_distance[ttype] > 0)
			    (void) DBSrPaintArea((Tile *)NULL, *bls.temps, &TiPlaneRect,
				    &CIFSolidBits, cifProcessResetFunc,
				    (ClientData)NULL);
	        }
	        else
		    DBSrPaintArea((Tile *)NULL, cellDef->cd_planes[bloats->bl_plane],
			    &TiPlaneRect, &bls.connect, cifProcessResetFunc,
			    (ClientData)NULL);

		break;

	    case CIFOP_SQUARES:
		if (hier)
		{
		    if ((op->co_next == NULL) || (op->co_next->co_opcode != CIFOP_GROW))
		    {
		    	hstop = TRUE;	/* Stop hierarchical processing */
		    	break;
		    }
		}
		if (CalmaContactArrays == FALSE)
		{
		    DBClearPaintPlane(nextPlane);
		    cifPlane = nextPlane;
		    cifSquaresFillArea(op, cellDef, curPlane);
		    temp = curPlane;
		    curPlane = nextPlane;
		    nextPlane = temp;
		}
		break;

	    case CIFOP_SQUARES_G:
		if (hier)
		{
		    if ((op->co_next == NULL) || (op->co_next->co_opcode != CIFOP_GROW))
		    {
		    	hstop = TRUE;	/* Stop hierarchical processing */
		    	break;
		    }
		}
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifSquaresFillArea(op, cellDef, curPlane);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_SLOTS:
		if (hier)
		{
		    if ((op->co_next == NULL) || (op->co_next->co_opcode != CIFOP_GROW))
		    {
		    	hstop = TRUE;	/* Stop hierarchical processing */
		    	break;
		    }
		}
		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifSlotsFillArea(op, cellDef, curPlane);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_MAXRECT:
		cifPlane = curPlane;

		DBClearPaintPlane(nextPlane);
		cifPlane = nextPlane;
		cifRectBoundingBox(op, cellDef, curPlane);
		temp = curPlane;
		curPlane = nextPlane;
		nextPlane = temp;
		break;

	    case CIFOP_NET:
		if (hier)
		{
		    hstop = TRUE;	/* Stop hierarchical processing */
		    break;
		}
		netname = (char *)op->co_client;
		cifPlane = curPlane;
		ttype = CmdFindNetProc(netname, CIFDummyUse, &bbox, FALSE);
		if (ttype != TT_SPACE)
		{
		    UndoDisable();
		    DBCellClearDef(Select2Def);
		    scx.scx_area = bbox;
		    scx.scx_use = CIFDummyUse;
		    scx.scx_trans = GeoIdentityTransform;
		    DBTreeCopyConnect(&scx, &DBConnectTbl[ttype], 0,
				DBConnectTbl, &TiPlaneRect, SEL_NO_LABELS, Select2Use);
		    cifSrTiles(op, area, Select2Def, temps, cifPaintFunc,
				(ClientData) CIFPaintTable);
		    DBCellClearDef(Select2Def);
		    UndoEnable();
		}
		break;

	    case CIFOP_BOUNDARY:
		if (hier)
		{
		    hstop = TRUE;	/* Stop hierarchical processing */
		    break;
		}
		cifPlane = curPlane;
		/* This function for cifoutput only.  cifinput handled separately. */

		if (origDef && (origDef->cd_flags & CDFIXEDBBOX))
		{
		    propvalue = (char *)DBPropGet(origDef, "FIXED_BBOX", &found);
		    if (!found) break;
		    if (sscanf(propvalue, "%d %d %d %d", &bbox.r_xbot, &bbox.r_ybot,
				&bbox.r_xtop, &bbox.r_ytop) != 4) break;

		    cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;
		    bbox.r_xbot *= cifScale;
		    bbox.r_xtop *= cifScale;
		    bbox.r_ybot *= cifScale;
		    bbox.r_ytop *= cifScale;
		    cifScale = 1;
		    DBNMPaintPlane(cifPlane, CIF_SOLIDTYPE, &bbox,
				CIFPaintTable, (PaintUndoInfo *)NULL);
		}
		break;

	    case CIFOP_BBOX:
		if (hier)
		{
		    hstop = TRUE;	/* Stop hierarchical processing */
		    break;
		}
		if (CIFErrorDef == NULL) break;

		/* co_client contains the flag (1) for top-level only */
		if ((int)op->co_client == 1)
		{
		    /* Only generate output for the top-level cell */
		    int found = 0;
		    CellUse *celluse;
		    for (celluse = CIFErrorDef->cd_parents;
				celluse != (CellUse *) NULL;
				celluse = celluse->cu_nextuse)
		    {
			if (celluse->cu_parent != (CellDef *) NULL)
			    if ((celluse->cu_parent->cd_flags & CDINTERNAL)
					!= CDINTERNAL)
			    {
			 	found = 1;
				break;
			    }
		    }
		    if (found != 0) break;
		}
		cifPlane = curPlane;
		bbox = CIFErrorDef->cd_bbox;
		cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;
		bbox.r_xbot *= cifScale;
		bbox.r_xtop *= cifScale;
		bbox.r_ybot *= cifScale;
		bbox.r_ytop *= cifScale;
		cifScale = 1;
		DBNMPaintPlane(curPlane, CIF_SOLIDTYPE, &bbox,
			CIFPaintTable, (PaintUndoInfo *)NULL);
		break;

	    /* The CIFOP_MASKHINTS operator checks the current cell for	*/
	    /* a property with "MASKHINTS_" followed by the name saved	*/
	    /* in the co_client record.  If there is such a property,	*/
	    /* then the property value is parsed for geometry in	*/
	    /* internal units, grouped in sets of four values llx lly	*/
	    /* urx ury.							*/

	    case CIFOP_MASKHINTS:
		{
		    int j, numfound;
		    char propname[512];
		    char *propptr;
		    char *layername = (char *)op->co_client;

		    sprintf(propname, "MASKHINTS_%s", layername);
		    
		    propvalue = (char *)DBPropGet(cellDef, propname, &found);
		    if (!found) break;	    /* No mask hints available */
		    propptr = propvalue;
		    while (*propptr)
		    {
			numfound = sscanf(propptr, "%d %d %d %d",
				&bbox.r_xbot, &bbox.r_ybot,
				&bbox.r_xtop, &bbox.r_ytop);

			if (numfound != 4)
			{
			    /* To do:  Allow keyword "rect", "tri", or "poly"
			     * at the start of the list and parse accordingly.
			     * For now, this only flags an error.
			     */
			    TxError("%s:  Cannot read rectangle values.\n", propname);
			    break;
			}
			cifPlane = curPlane;
			cifScale = (CIFCurStyle) ? CIFCurStyle->cs_scaleFactor : 1;
			bbox.r_xbot *= cifScale;
			bbox.r_xtop *= cifScale;
			bbox.r_ybot *= cifScale;
			bbox.r_ytop *= cifScale;
			cifScale = 1;
			DBNMPaintPlane(curPlane, CIF_SOLIDTYPE, &bbox,
				CIFPaintTable, (PaintUndoInfo *)NULL);
			for (j = 0; j < 4; j++)
			{
			    while (*propptr && isspace(*propptr)) propptr++;
			    while (*propptr && !isspace(*propptr)) propptr++;
			}
		    }
		}
		break;

	    default:
		continue;
	}
	if (hstop) break;	/* Don't process any further rules */
    }

    return curPlane;
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFGen --
 *
 * 	This procedure generates a complete set of CIF layers for
 *	a particular area of a particular cell.  NOTE: if the argument
 *	genAllPlanes is FALSE, only planes for those layers having
 *	a bit set in 'layers' are generated; the others are set
 *	to NULL.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	The parameters realPlanes and tempPlanes are modified
 *	to hold the CIF and temporary layers for area of cellDef,
 *	as determined by the current CIF generation rules.
 *
 * ----------------------------------------------------------------------------
 */

void
CIFGen(cellDef, origDef, area, planes, layers, replace, genAllPlanes, hier, clientdata)
    CellDef *cellDef;		/* Cell for which CIF is to be generated. */
    CellDef *origDef;		/* Original cell, if different from cellDef */
    Rect *area;			/* Any CIF overlapping this area (in coords
				 * of cellDef) will be generated.  The CIF
				 * will be clipped to this area.
				 */
    Plane **planes;		/* Pointer to array of pointers to planes
				 * to hold "real" CIF layers that are
				 * generated.  Pointers may initially be
				 * NULL.
				 */
    TileTypeBitMask *layers;	/* CIF layers to generate. */
    bool replace;		/* TRUE means that the new CIF is to replace
				 * anything that was previously in planes.
				 * FALSE means that the new CIF is to be
				 * OR'ed in with the current contents of
				 * planes.
				 */
    bool genAllPlanes;		/* If TRUE, generate a tile plane even for
				 * those layers not specified as being
				 * generated in the 'layers' mask above.
				 */
    bool hier;			/* TRUE if called from CIFGenSubcells or CIFGenArrays */
    ClientData clientdata;	/* Data that may be passed along to the
				 * CIF operation functions.
				 */
{
    int i;
    Plane *new[MAXCIFLAYERS];
    Rect expanded, clip;

    /*
     * Generate the area in magic coordinates to search, and the area in
     * cif coordinates to use in clipping the results of CIFGenLayer().
     */
    cifGenClip(area, &expanded, &clip);

    /*
     * Generate all of the new layers in a temporary place.
     * If a layer isn't being generated, leave new[i] set to
     * NULL to indicate this fact.
     */
    for (i = 0; i < CIFCurStyle->cs_nLayers; i++)
    {
	if (TTMaskHasType(layers,i))
	{
	    CIFErrorLayer = i;
	    new[i] = CIFGenLayer(CIFCurStyle->cs_layers[i]->cl_ops,
		    &expanded, cellDef, origDef, new, hier, clientdata);

	    /* Clean up the non-manhattan geometry in the plane */
	    if (CIFUnfracture) DBMergeNMTiles(new[i], &expanded,
			(PaintUndoInfo *)NULL);
	}
	else if (genAllPlanes) new[i] = DBNewPlane((ClientData) TT_SPACE);
	else new[i] = (Plane *) NULL;
    }

    /*
     * Now mask off all the unwanted material in the new layers, and
     * either OR them into the existing layers or replace the existing
     * material with them.
     */
    for (i = 0; i < CIFCurStyle->cs_nLayers; i += 1)
    {
	if (new[i])
	    cifClipPlane(new[i], &clip);

	if (replace)
	{
	    if (planes[i])
	    {
		DBFreePaintPlane(planes[i]);
		TiFreePlane(planes[i]);
	    }
	    planes[i] = new[i];
	    continue;
	}

	if (planes[i])
	{
	    if (new[i])
	    {
		cifPlane = planes[i];
		cifScale = 1;
		(void) DBSrPaintArea((Tile *) NULL, new[i], &TiPlaneRect,
			&CIFSolidBits, cifPaintFunc,
			(ClientData) CIFPaintTable);
		DBFreePaintPlane(new[i]);
		TiFreePlane(new[i]);
	    }
	}
	else planes[i] = new[i];
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifClipPlane --
 *
 * Erase the portions of the plane 'plane' that lie outside of 'clip'.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	See above.
 *
 * ----------------------------------------------------------------------------
 */

void
cifClipPlane(plane, clip)
    Plane *plane;
    Rect *clip;
{
    Rect r;

    if (clip->r_xtop < TiPlaneRect.r_xtop)
    {
	r = TiPlaneRect;
	r.r_xbot = clip->r_xtop;
	DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_ytop < TiPlaneRect.r_ytop)
    {
	r = TiPlaneRect;
	r.r_ybot = clip->r_ytop;
	DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_xbot > TiPlaneRect.r_xbot)
    {
	r = TiPlaneRect;
	r.r_xtop = clip->r_xbot;
	DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
    if (clip->r_ybot > TiPlaneRect.r_ybot)
    {
	r = TiPlaneRect;
	r.r_ytop = clip->r_ybot;
	DBPaintPlane(plane, &r, CIFEraseTable, (PaintUndoInfo *) NULL);
    }
}

/*
 * ----------------------------------------------------------------------------
 *
 * cifGenClip --
 *
 * Compute two new areas from the original area:  one ('expanded')
 * is expanded by a CIF halo and is used to determine how much of
 * the database to search to find what's relevant for CIF generation;
 * the other ('clip') is the CIF equivalent of area and is used to
 * clip the resulting CIF.  This code is tricky because area may run
 * off to infinity, and we have to be careful not to expand past infinity.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Sets *expanded and *clip.
 *
 * ----------------------------------------------------------------------------
 */

void
cifGenClip(area, expanded, clip)
    Rect *area;			/* Any CIF overlapping this area (in coords
				 * of cellDef) will be generated.  The CIF
				 * will be clipped to this area.
				 */
    Rect *expanded, *clip;
{
    if (area->r_xbot > TiPlaneRect.r_xbot)
    {
	clip->r_xbot = area->r_xbot * CIFCurStyle->cs_scaleFactor;
	expanded->r_xbot = area->r_xbot - CIFCurStyle->cs_radius;
    }
    else clip->r_xbot = expanded->r_xbot = area->r_xbot;
    if (area->r_ybot > TiPlaneRect.r_ybot)
    {
	clip->r_ybot = area->r_ybot * CIFCurStyle->cs_scaleFactor;
	expanded->r_ybot = area->r_ybot - CIFCurStyle->cs_radius;
    }
    else clip->r_ybot = expanded->r_ybot = area->r_ybot;
    if (area->r_xtop < TiPlaneRect.r_xtop)
    {
	clip->r_xtop = area->r_xtop * CIFCurStyle->cs_scaleFactor;
	expanded->r_xtop = area->r_xtop + CIFCurStyle->cs_radius;
    }
    else clip->r_xtop = expanded->r_xtop = area->r_xtop;
    if (area->r_ytop < TiPlaneRect.r_ytop)
    {
	clip->r_ytop = area->r_ytop * CIFCurStyle->cs_scaleFactor;
	expanded->r_ytop = area->r_ytop + CIFCurStyle->cs_radius;
    }
    else clip->r_ytop = expanded->r_ytop = area->r_ytop;
}

/*
 * ----------------------------------------------------------------------------
 *
 * CIFClearPlanes --
 *
 * 	This procedure clears out a collection of CIF planes.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	Each of the planes in "planes" is re-initialized to point to
 *	an empty paint plane.
 *
 * ----------------------------------------------------------------------------
 */

void
CIFClearPlanes(planes)
    Plane **planes;		/* Pointer to an array of MAXCIFLAYERS
				 * planes.
				 */
{
    int i;

    for (i = 0; i < MAXCIFLAYERS; i++)
    {
	if (planes[i] == NULL)
	{
	    planes[i] = DBNewPlane((ClientData) TT_SPACE);
	}
	else
	{
	    DBClearPaintPlane(planes[i]);
	}
    }
}
